题目链接：https://ac.nowcoder.com/acm/contest/1099/I
有一颗 n 个点的带权树，点的编号是 1, 2, …, n. 树有 (n - 1) 条边，求树上两点之间的距离是2019的倍数的点对有多少？
点对距离计数：点分治 点分治关键是对cal函数进行修改，其他的基本不用改。如何灵活运用cal函数，主要还是要理解几个变量的含义。根据点分治的过程，是不断找重心，然后<1>求出每个点到重心的距离</1>，同时用一个数组temp记录这些距离，再对各个子树进行分治，过程一样。而cal函数就是在计算完<1>后，对temp进行操作，怎么改，看具体的题目。这里有个点需要注意，就是<1>操作会把所有点到重心的距离也算进去（加入传入重心，就会有一个零），所以temp必然会包含一个len（len是calc的参数）。总的来说calc就是计算完其他点到某一点的距离后，对这些点的距离进行处理的中间过程。 cal改法
int cc[2019]; inline int calc(int x,int len) { dis[x] = len; temp[0] = 0;//temp[0]记录temp数组的长度 dfs(0,x); memset(cc,0,sizeof(cc)); for(int i=1;i<=temp[0];i++) cc[temp[i] 19]++; cc[0]--; int res=cc[0]*(cc[0]+1)/2; for(int i=1;i<=1009;i++) res+=cc[i]*cc[2019-i]; return res; }2019倍数，很容易想到取余处理，设B为重心，A->B+B->C=2019，就说明A->C是2019的倍数。 这样其实还有一个问题，就是重复计算。下面通过图解，解释如何处理。 A为重心，每一点到重心距离已经得到，但是通过cal函数会把B->A和C->A的距离也加上，所以需要把这种可能排除，我们最终的结果是，记录每次分治不同子树之间的距离，而同一子树之间的点对需要排除。如何排除，ans-=cal(H,c)即可，对H的子节点到H的距离点对加上c，这些答案需要排除。
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false) const int N = 20020, INF = 0x7f7f7f7f; int n,head[N*2],num,tot,ans;//tot记录当前子树点数 int dis[N],flag[N],temp[N]; //dis记录子树每一点到根节点的距离，flag用于删除根节点，temp总汇到根节点的距离 int size[N],Max[N],root; struct edge { int next,to,len; } G[N*2]; void add(int from,int to,int len) { G[++num].next=head[from]; G[num].to=to; G[num].len=len; head[from]=num; } inline void input(void) { for (int i=1; i<n; i++) { int x,y,v; cin>>x>>y>>v; add(x,y,v), add(y,x,v); } } inline void dp(int fa,int cur)//求树的重心 { size[cur] = 1, Max[cur] = 0; for (int i=head[cur]; i; i=G[i].next) { int v = G[i].to; if ( flag[v] || v == fa ) continue; dp(cur,v); size[cur] += size[v]; Max[cur] = max( Max[cur], size[v] ); } Max[cur] = max( Max[cur], tot - size[cur] ); if ( Max[root] > Max[cur] ) root = cur; } inline void dfs(int fa,int cur) { temp[ ++temp[0] ] = dis[cur]; for (int i=head[cur]; i; i=G[i].next) { int v = G[i].to; if ( v == fa || flag[v] ) continue; dis[v] = dis[cur] + G[i].len; dfs(cur,v); } } int cc[2019]; inline int calc(int x,int len) { dis[x] = len; temp[0] = 0;//temp[0]记录temp数组的长度 dfs(0,x); memset(cc,0,sizeof(cc)); for(int i=1;i<=temp[0];i++) cc[temp[i] 19]++; cc[0]--; int res=cc[0]*(cc[0]+1)/2; for(int i=1;i<=1009;i++) res+=cc[i]*cc[2019-i]; return res; } inline void divide(int x) { flag[x] = true;//删去根节点 ans += calc(x,0); //cout<<"ans="<<ans<<"\n"; for (int i=head[x]; i; i=G[i].next) { int y = G[i].to; if ( flag[y] ) continue; ans -= calc(y,G[i].len);//点对在同一子树的情况 tot = size[y], root = 0; dp(0,y); divide(root); } } inline void reset(void) { num = 0; memset( head, 0, sizeof head ); memset( flag, 0, sizeof flag ); ans = 0, tot = n; root = 0, Max[0] = INF; } int main(void) { IOS; while(cin>>n) { reset(); input(); dp(0,1); divide(root); cout<<ans<<"\n"; //cout<<"\n"; } return 0; }