1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define INF 0x3fffffff 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n) 7 #define N 40010 8 using namespace std; 9 10 //general 11 int n,k,ans; 12 13 //edge 14 struct e{int t,w,n;}; e es[N*2]; int ess,g[N]; 15 inline void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;} 16 17 //pointapart点分治相关 英语渣求谅解 18 int root/*子树的根*/,sm/*子树大小，中间搜索时用*/,mn,szs/*data数组大小*/,d[N]/*距离*/,sz[N]/*子树大小*/,data[N]/*用于排序*/; bool vis[N]; 19 void getroot(int x,int fa){//求树的重心 20 sz[x]=1; int mx=0; 21 visit(i,x)if(! vis[es[i].t]&&es[i].t!=fa){getroot(es[i].t,x); sz[x]+=sz[es[i].t]; mx=max(mx,sz[es[i].t]);} 22 mx=max(mx,sm-sz[x]); if(mx<mn)root=x,mn=mx; 23 } 24 void getdis(int x,int fa){//求距离 25 data[++szs]=d[x]; 26 visit(i,x)if(! vis[es[i].t]&&es[i].t!=fa){d[es[i].t]=d[x]+es[i].w; getdis(es[i].t,x);} 27 } 28 int calc(int x,int st){//计算点对数 29 d[x]=st; szs=0; getdis(x,-1); sort(data+1,data+szs+1); int l=1,r=szs,a=0; 30 while(l<r){if(data[l]+data[r]<=k)a+=(r-l),l++;else r--;} 31 return a; 32 } 33 void work(int x){//主分治过程 34 ans+=calc(x,0); vis[x]=1; 35 visit(i,x)if(!vis[es[i].t]){ans-=calc(es[i].t,es[i].w); root=es[i].t; sm=sz[es[i].t]; mn=INF; getroot(es[i].t,x); work(root);} 36 } 37 38 int main(){ 39 //freopen("zs.txt","r",stdin); 40 scanf("%d",&n); ess=0; memset(g,-1,sizeof(g)); 41 inc(i,1,n-1){int a,b,c; scanf("%d%d%d",&a,&b,&c); pe(a,b,c);} scanf("%d",&k); 42 memset(vis,0,sizeof(vis)); root=1; mn=INF; getroot(1,-1); ans=0; work(root); printf("%d\n",ans); 43 return 0; 44 }
引入一个概念：树的重心：找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
很明显，我们找根就要找树的重心。怎么求树的重心呢？用dfs求出当前节点所在子树的每个节点最大子树的最小值即可，注意树的形态是不一定的，所以除了逻辑上的儿子sz[i]还有sm-sz[x]
同时还有一些细节，比如vis数组，使搜索时不要搜到想搜的子树之外的节点
时间复杂度？work执行n次，calc执行O(log2n)次（因为根为树的重心），getroot和getdis总共执行了O(nlog2n)次，所以总复杂度为O(nlog2n)（其实我也不知道为什么复杂度是这个，但它就是这个……）
原文：http://www.cnblogs.com/YuanZiming/p/5037443.html