题解 P2634 【聪聪可可】

这道题是点分治的模板题。 作为一个蒟蒻，我学习一个算法都是从看图解、看代码开始。一个模板题是新手练手之处，自应有详细的代码解释让他们理解程序，继而理解算法。~~因而楼下代码简短的注释对新手不太友好~~ 在一些树上路径问题中，暴力求解时间复杂度过高，往往需要一些更为高效的算法，点分治就是其中之一。 【流程】 1、首先选取一个点，把无根树变成有根树。 那么如何选点呢？ ——树型动规 因为树是递归定义的，所以我们当然希望递归的层数最小。 每次选取的点，要保证与此点相连的结点数最多的连通块的结点数最小，我们把这个点叫做“重心”。 那么找到一颗树的重心有以下算法： （1）dfs一次，算出以每个点为根的子树大小。 （2）记录以每个结点为根的最大子树的大小。 （3）判断：如果以当前结点为根的最大子树大小比当前根更优，更新当前根。 2、处理联通块中通过根结点的路径。 3、标记根结点（相当于处理过后，将根结点从子树中删除）。 4、递归处理以当前点的儿子为根的每棵子树。 本题核心思想：明显的树上的点分治，利用数组t[]表示搜当前根的子树时，当前子树之前的路径长x的方案数。最终答案为当前子树路径长x的方案数 \*ans+=g[j]\*ff[(3-j)%3]\*2。 注意（１，１）合法，（１，２）（２，１）算两种。 ```cpp #include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #define fp(i,a,b) for(int i=a;i<=b;i++) #define fq(i,a,b) for(int i=a;i>=b;i--) #define il inline #define re register #define ll long long using namespace std; const int N=20005; int n,cnt=0,root,sum,ans,t[5],h[N],f[N],son[N]={},d[N]={}; bool vis[N]={}; struct Edge { int to,next,w; }e[N<<1]; il int gi() { int x=0; short int t=1; char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t; } void add(int u,int v,int w) { e[++cnt]=(Edge){v,h[u],w};h[u]=cnt; } void getdeep(int u,int fa) { t[d[u]]++; for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(v==fa||vis[v]) continue; d[v]=(d[u]+e[i].w)%3; getdeep(v,u); } } int calc(int u,int v) { t[0]=t[1]=t[2]=0; d[u]=v; getdeep(u,0); return t[1]*t[2]*2+t[0]*t[0]; } void getroot(int u,int fa)//u表示当前结点，fa表示u的父结点 { son[u]=1; f[u]=0;//f数组记录以u为根的最大子树的大小 for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa&&!vis[v])//避免陷入死循环 { getroot(v,u);//得到子结点信息 son[u]+=son[v];//计算u结点大小 f[u]=max(f[u],son[v]);//更新f数组 } } f[u]=max(f[u],sum-son[u]);//sum表示当前树的大小，因为以x为根的情况还要考虑以x的父亲为根的子树大小。 if(f[u]<f[root]) root=u;//更新当前根 } void solve(int u) { ans+=calc(u,0); vis[u]=1;//将当前点标记 for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(vis[v]) continue; ans-=calc(v,e[i].w); root=0;//初始化根 sum=son[v];//初始化sum getroot(v,0);//找连通块的根 solve(root);//递归处理下一个连通块 } } int gcd(int a,int b) { return (!b)?a:gcd(b,a%b); } int main() { n=gi(); fp(i,1,n-1) { int u=gi(),v=gi(),w=gi()%3; add(u,v,w);add(v,u,w);//建树 } sum=f[0]=n;//初始化sum和f[0] root=0;//初始化root getroot(1,0);//找根 solve(root);//点分治 int t=gcd(ans,n*n); printf("%d/%d\n",ans/t,n*n/t); return 0; } ps:蒟蒻初学此算法，如有疑问或题解有不当之处请私信我。 ```