树的重心: 假设有unordered_map<int,vector<int>> m 表示与结点关联的结点 void dfs(int v,int fa){ son[v] = 0; int d = G[v].size(); int prebalance = 0; for(int i=0;i<d;i++){ int k = G[v][i]; if(k==fa) continue; son[v] += son[u]+1; prebalance = max(prebalance,son[u]+1); } prebalance = max(prebalance,n-son[v]-1); if(prebalance<balance || balance == prebalance && v<ans){ balance = prebalance; ans = v; } } 树的最长路径: int lastorder(int pre,int cur){ int first = 0, second = 0; for(int i = 0;i<G[cur].size();i++){ if(G[cur][i]==pre) continue; int temp = lastorder(cur,G[cur][i]); if(temp>first){ second = first; first = temp; }else if(temp>second){ second = temp; } } maxdistance = max(maxdistance,first+second); return first+1; }