POJ 1655 求树的重心
求树的重心模版题,$O(N)$为何网络上都说$O(nlogn)$或者$O(n^2)$
明明每个点访问一次,每条边访问一次,$O(n+n-1)$也就是$O(n)$。
代码来啦:
# include <stdio.h> # include <vector> using namespace std; int n,size[100010]; vector<int> G[100010]; int asize,s; void dfs(int x,int father) { size[x]=0; int balance=0; for (int i=0;i<G[x].size();++i) { int to=G[x][i]; if(to==father) continue; dfs(to,x); size[x]+=size[to]+1; balance=max(balance,size[to]+1); } balance=max(balance,n-size[x]-1); if(balance<asize || (balance==asize && x<s)) { asize=balance; s=x; } } int LBW; int main() { scanf("%d",&LBW); while(LBW--) { scanf("%d",&n); for (int i=0;i<=n;++i) { G[i].clear(); size[i]=0; } for (int i=1,a,b;i<n;++i) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } asize=(1<<30); dfs(1,0); printf("%d %d\n",s,asize); } return 0; }