樹的重心和直徑

樹的重心

性質：

1. 最大的子樹最小
2. 找到一個點,其所有的子樹中最大的子樹節點數最少,那麼這個點就是這棵樹的重心,删去重心後，生成的多棵樹盡可能平衡
3. 樹中所有點到某個點的距離和中，到重心的距離和是最小的，如果有兩個距離和，他們的距離和一樣，則這兩個點都是重心（即重心可以有兩個）
4. 把兩棵樹通過一條邊相連，新的樹的重心在原來兩棵樹重心的連線上
5. 一棵樹添加或者删除一個節點，樹的重心最多隻移動一條邊的位置
6. 一棵樹最多有兩個重心，且相鄰。

思路：

1. 任選節點r為根節點做dfs，dfs的同時即更新所有的d(目前子樹的大小)，以及最小的最大子樹，注意目前子樹的最大子樹要考慮其父節點向上的樹
2. 最後得到的包含最小的最大子樹的節點就是重心了

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||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<mx) mx=mm, heart=u;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    mx=inf, n=read();
    for(int i=1; i<n; ++i) add_edge(read(),read());
    dfs(1,0);
    printf("%d\n", heart);
}
           

樹的直徑

算法 1 1 1：任選節點 u u u做 d f s dfs dfs，找到最遠節點 v v v；再從 v v v做 d f s dfs dfs，找到最遠節點 w w w，則 v − w v-w v−w即為最長路徑， d i s ( v , w ) dis(v,w) dis(v,w)即為樹的直徑。

适合于邊權非負的情形，代碼簡單，是以先不給出算法 1 1 1的代碼QAQ

算法 2 2 2：任選節點 r r r作為根節點，求出最遠距離 f f f和次遠距離 s s s(在不同子樹上)，則樹的直徑為 f + s f+s f+s。

适用于所有情形

#include<cstdio>
#include<vector>
#include<cstring>
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 <Node> G[maxn];
void DFS(int x){
	f[x]=s[x]=0;
	for(int i=0;i<G[x].size();i++){
		Node v=G[x][i];
		if (!vis[v.to]){
			vis[v.to]=true;
			DFS(v.to);//通路子節點。
			vis[v.to]=false;
			if(f[x]<f[v.to]+v.val){//如果發現了一條更長的路徑，那麼更新f[x]和g[x]。
				s[x]=f[x];//原來的f[x]變為次長路，新發現的記為最長路。
				f[x]=f[v.to]+v.val;
			}
			else if(s[x]<f[v.to]+v.val) s[x]=f[v.to]+v.val;//如果找到了一條比次長路更長的路徑，那麼更新g[x]。
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v,val;
		scanf("%d%d%d",&u,&v,&val);
		G[u].push_back(Node(v,val));
		G[v].push_back(Node(u,val));
	}
    int root=1; //随便選一個節點就行了
	vis[root]=true;
	DFS(root);
	printf("%d\n",f[root]+s[root]);
	return 0;
}