나무의 중심 과 지름

나무의 중심
성질:

가장 큰 나무 가 가장 작다

한 가지 점 을 찾 았 는데 그 모든 나무 중에서 가장 큰 나무 노드 수가 가장 적다. 그러면 이 점 이 바로 이 나무의 중심 이다. 중심 을 지 운 후에 생 성 된 여러 그루 의 나 무 는 가능 한 한 균형 을 이룬다

나무 에 있 는 모든 점 에서 특정한 점 까지 의 거리 와 중, 중심 까지 의 거리 와 가장 작은 것 이다. 만약 에 두 개의 거리 와 그들의 거리 가 같다 면 이 두 가지 점 은 모두 중심 (즉 중심 은 두 개 일 수 있다)

이다.

두 그루 의 나 무 를 한 변 을 통 해 연결 시 키 고 새로운 나무의 중심 은 원래 두 그루 의 나무 중심 연결선 에 있다

나무 한 그루 에 노드 를 추가 하거나 삭제 합 니 다. 나무의 중심 은 한 변 의 위치 만 이동 합 니 다

한 그루 의 나 무 는 최대 두 개의 중심 이 있 고 인접 해 있다.

생각:

선택 한 노드 r 를 루트 노드 로 dfs 를 만 들 고 dfs 를 하 는 동시에 모든 d (현재 하위 트 리 의 크기) 와 가장 작은 최대 하위 트 리 를 업데이트 합 니 다. 현재 하위 트 리 의 최대 하위 트 리 는 부모 노드 가 위로 향 하 는 트 리

를 고려 해 야 합 니 다.

마지막 으로 얻 은 가장 작은 하위 나 무 를 포함 하 는 노드 가 중심 이다

#include "bits/stdc++.h"
#define hhh printf("hhh
")
#define see(x) (cerr< pr;
inline int read() {int x=0;char c=getchar();while(c'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, heart, mx, sz[maxn];
int head[maxn], to[maxn*2], nxt[maxn*2], tot;

inline void add_edge(int u, int v) {
    ++tot, to[tot]=v, nxt[tot]=head[u], head[u]=tot;
    ++tot, to[tot]=u, nxt[tot]=head[v], head[v]=tot;
}

void dfs(int u, int fa) {
    sz[u]=1; int mm=0;
    for(int i=head[u]; i; i=nxt[i]) {
        int v=to[i];
        if(v!=fa) {
            dfs(v,u);
            sz[u]+=sz[v];
            if(sz[v]>mm) mm=sz[v];
        }
    }
    if(n-sz[u]>mm) mm=n-sz[u];
    if(mm

나무의 지름
알고리즘 1 1 1: 노드 u u 를 선택 하여 d f s dfs dfs 를 만 들 고 가장 먼 노드 v v v 를 찾 습 니 다.v v 에서 d f s dfs dfs dfs 를 만 들 고 가장 먼 노드 w w 를 찾 으 면 v - w v - w v - w 는 가장 긴 경로 이 고 d i s (v, w) dis (v, w) dis (v, w) 는 나무의 지름 이다.변 권 이 마이너스 가 아 닌 경우 에 적합 하고 코드 가 간단 하기 때문에 알고리즘 11 의 코드 QAQ 를 제시 하지 않 습 니 다.
알고리즘 2222: 노드 r r r 를 루트 노드 로 선택 하여 가장 원 거리 f f f 와 차 원 거리 s s (서로 다른 하위 트 리 에서) 를 구하 면 나무의 직경 은 f + s f + s f + s. s 입 니 다.모든 상황 에 적용

#include
#include
#include
using namespace std;
const int maxn=10100;
int n,ans;
int f[maxn],s[maxn];//f     ，g     。
bool vis[maxn];
struct Node{
	int to,val;
	Node(int to=0,int val=0):to(to),val(val){}
};
vector  G[maxn];
void DFS(int x){
	f[x]=s[x]=0;
	for(int i=0;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

나무의 중심 과 지름

두 그루 의 나 무 를 한 변 을 통 해 연결 시 키 고 새로운 나무의 중심 은 원래 두 그루 의 나무 중심 연결선 에 있다 선택 한 노드 r 를 루트 노드 로 dfs 를 만 들 고 dfs 를 하 는 동시에 모든 d...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

나무의 중심 과 지름

좋은 웹페이지 즐겨찾기