题目链接：Tree
树分治参考资料：09年漆子超 ZigZagK的博客 【点分治】的学习笔记和众多例题
以上的资料是我看过好的，具体算法分析实现都讲明白，贴一下我的代码（由于poj交不了题还没a）
1 #include<bits/stdc++.h> 2 #include<set> 3 #include<cstdio> 4 #include<iomanip> 5 #include<iostream> 6 #include<string> 7 #include<cstring> 8 #include<algorithm> 9 #define pb push_back 10 #define ll long long 11 #define fi first 12 #define se second 13 #define PI 3.14159265 14 #define ls l,m,rt<<1 15 #define rs m+1,r,rt<<1|1 16 #define eps 1e-7 17 #define pii pair<int,int> 18 typedef unsigned long long ull; 19 const int mod=1e3+5; 20 const ll inf=0x3f3f3f3f3f3f3f; 21 const int maxn=1e5+5; 22 using namespace std; 23 int n,m,head[maxn],to[maxn*2],w[maxn*2],nxt[maxn*2],cnt,k,siz[maxn],dep[maxn],rt,mx[maxn],s; 24 int now[maxn]; 25 bool vis[maxn]; 26 ll ans; 27 void add_edge(int x,int y,int l) 28 { 29 to[++cnt]=y;w[cnt]=l;nxt[cnt]=head[x];head[x]=cnt; 30 } 31 void dfs_rt(int v,int f)//找重心 32 { 33 siz[v]=1;mx[v]=0; 34 //cout<<v<<"SSS"<<f<<endl; 35 for(int i=head[v];i;i=nxt[i]) 36 { 37 if(to[i]==f||vis[to[i]])continue; 38 dfs_rt(to[i],v); 39 siz[v]+=siz[to[i]]; 40 mx[v]=max(siz[to[i]],mx[v]); 41 } 42 mx[v]=max(s-siz[v],mx[v]); 43 if(rt==-1||mx[v]<mx[rt])rt=v; 44 } 45 void get_dep(int v,int f) 46 { 47 now[++now[0]]=dep[v]; 48 for(int i=head[v];i;i=nxt[i]) 49 { 50 if(vis[to[i]]||to[i]==f)continue; 51 dep[to[i]]=dep[v]+w[i]; 52 get_dep(to[i],v); 53 } 54 } 55 int get_sum(int v,int dis) 56 { 57 int cn=0;now[0]=0; 58 dep[v]=dis;get_dep(v,-1); 59 sort(now+1,now+1+now[0]); 60 int l=1,r=now[0]; 61 while(l<r)if(now[l]+now[r]<=k)cn+=r-l,l++;else r--; 62 return cn; 63 } 64 void get_ans(int v) 65 { 66 vis[v]=true;ans+=get_sum(v,0); 67 cout<<"###"<<ans<<endl; 68 for(int i=head[v];i;i=nxt[i]) 69 { 70 if(vis[to[i]])continue; 71 ans-=get_sum(to[i],w[i]); 72 cout<<"SSS"<<ans<<endl; 73 rt=-1;s=siz[to[i]];dfs_rt(to[i],v); 74 get_ans(rt); 75 } 76 } 77 int main() 78 { 79 while(~scanf("%d %d",&n,&k)) 80 { 81 if(!n&&!k)break; 82 memset(head,0,sizeof(head));cnt=0; 83 memset(vis,0,sizeof(vis)); 84 for(int i=0;i<n-1;i++) 85 { 86 int u,v,l; 87 scanf("%d %d %d",&u,&v,&l); 88 add_edge(u,v,l);add_edge(v,u,l); 89 } 90 rt=-1;s=n;dfs_rt(1,-1); 91 get_ans(rt); 92 printf("%lld\n",ans); 93 } 94 return 0; 95 }
第二个例题：2152: 聪聪可可
题解跟上面那题差不多，计算出的到根的距离%3之后的值的个数，now[0],now[1],now[2].答案就是now[0]*now[0]+2*now[1]*now[2]
1 #include<bits/stdc++.h> 2 #include<set> 3 #include<cstdio> 4 #include<iomanip> 5 #include<iostream> 6 #include<string> 7 #include<cstring> 8 #include<algorithm> 9 #define pb push_back 10 #define ll long long 11 #define fi first 12 #define se second 13 #define PI 3.14159265 14 #define ls l,m,rt<<1 15 #define rs m+1,r,rt<<1|1 16 #define eps 1e-7 17 #define pii pair<int,int> 18 typedef unsigned long long ull; 19 const int mod=1e3+5; 20 const ll inf=0x3f3f3f3f3f3f3f; 21 const int maxn=2e4+5; 22 using namespace std; 23 int n,m,head[maxn],to[maxn*2],w[maxn*2],nxt[maxn*2],cnt,k,siz[maxn],dep[maxn],rt,mx[maxn],s; 24 int now[maxn]; 25 bool vis[maxn]; 26 int ans; 27 void add_edge(int x,int y,int l) 28 { 29 to[++cnt]=y;w[cnt]=l;nxt[cnt]=head[x];head[x]=cnt; 30 } 31 void dfs_rt(int v,int f)//找重心 32 { 33 siz[v]=1;mx[v]=0; 34 for(int i=head[v];i;i=nxt[i]) 35 { 36 if(to[i]==f||vis[to[i]])continue; 37 dfs_rt(to[i],v); 38 siz[v]+=siz[to[i]]; 39 mx[v]=max(siz[to[i]],mx[v]); 40 } 41 mx[v]=max(s-siz[v],mx[v]); 42 if(rt==-1||mx[v]<mx[rt])rt=v; 43 } 44 void get_dep(int v,int f) 45 { 46 now[(dep[v])%3]++; 47 for(int i=head[v];i;i=nxt[i]) 48 { 49 if(vis[to[i]]||to[i]==f)continue; 50 dep[to[i]]=dep[v]+w[i]; 51 get_dep(to[i],v); 52 } 53 } 54 int get_sum(int v,int dis) 55 { 56 int cn=0;now[0]=0,now[1]=0,now[2]=0; 57 dep[v]=dis;get_dep(v,-1); 58 cn+=now[0]*now[0]+2*now[1]*now[2]; 59 return cn; 60 } 61 void get_ans(int v) 62 { 63 vis[v]=true;ans+=get_sum(v,0); 64 for(int i=head[v];i;i=nxt[i]) 65 { 66 if(vis[to[i]])continue; 67 ans-=get_sum(to[i],w[i]); 68 rt=-1;s=siz[to[i]];dfs_rt(to[i],v); 69 get_ans(rt); 70 } 71 } 72 int main() 73 { 74 while(~scanf("%d",&n)) 75 { 76 memset(head,0,sizeof(head));cnt=0; 77 memset(vis,0,sizeof(vis)); 78 for(int i=0;i<n-1;i++) 79 { 80 int u,v,l; 81 scanf("%d %d %d",&u,&v,&l); 82 add_edge(u,v,l);add_edge(v,u,l); 83 } 84 rt=-1;s=n;dfs_rt(1,-1); 85 get_ans(rt); 86 int sum=n*n; 87 int tmp=__gcd(sum,ans); 88 89 ans/=tmp;sum/=tmp; 90 printf("%d/%d\n",ans,sum); 91 } 92 return 0; 93 }
原文：https://www.cnblogs.com/lhclqslove/p/9345665.html
