题目链接：
D. Fish eating fruit
题意：一颗树，有边权，定义a->b的路径为树上的最短路，分别计算路径长度取余3为0的路径和，取余为1的所有的路径和，2的~，结果对
1
e
9
+
7
1e9+7
1
e
9
+
7
取模。
数据范围：保证所有的n加起来
<
=
1
0
5
<=10^5
<
=
1
0
5
，边权
<
=
1
0
5
<=10^5
<
=
1
0
5
该题a->b与b->a算两种路径。
树上的路径可以分为两种情况：
- 经过根节点的路径
- 完全位于根节点一颗子树内部的路径，不经过根节点
对于第二种路径通过点分治分治计算，对于第一种路径，分别记录子树内经过根节点三种路径出现的次数，以及三种路径分别的和，每次从重心划分成各个联通块，枚举12种情况，暴力计算答案即可。
只经过重心的一颗子树内的答案，以及经过两颗子树的答案，统计即可。
复杂度：
O
(
n
∗
l
o
g
2
n
)
O(n*log_2n)
O
(
n
∗
l
o
g
2
n
)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
bool vis[maxn];
bool flag[maxn];
int size1[maxn];//以i为根的子树大小;
int res;
struct Edge{
int v,w,next;
}edge[maxn<<1];
int head[maxn],top;
int d[maxn];
void add(int u,int v,int w){
edge[top].v=v;
edge[top].w=w;
edge[top].next=head[u];
head[u]=top++;
}
void init(){
top=0;
res=0;
memset(head,-1,sizeof(head));
memset(flag,0,sizeof(flag));
memset(size1,0,sizeof(size1));
memset(d,0,sizeof(d));
}
int rt;//树的重心;
int ans;
int n,k;
//求解节点个数为zong个,的树的重心;
void get_rt(int u,int zong){
vis[u]=1;
size1[u]=1;
int maxx=0;
int v;
for(int i=head[u];i!=-1;i=edge[i].next){
v=edge[i].v;
if(vis[v]||flag[v]) continue;
get_rt(v,zong);
size1[u]+=size1[v];
maxx=max(maxx,size1[v]);
}
maxx=max(maxx,zong-size1[u]);
if(maxx<ans){
ans=maxx;
rt=u;
}
}
struct Node{
ll s0,s1,s2,n0,n1,n2;
}in;
vector<Node> vv;//保存不同子树中的六元组;
const int mod=1e9+7;
//求解b,d数组,同时记录a,cnt数组;
ll s0,s1,s2,n0,n1,n2;
void dfs(int u,int fa){//计算子树;
if(d[u]%3==0){
s0+=d[u];
s0%=mod;
++n0;
}
else if(d[u]%3==1){
s1+=d[u];
s1%=mod;
++n1;
}
else{
s2+=d[u];
s2%=mod;
++n2;
}
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(vis[v]||flag[v]) continue;
d[v]=d[u]+edge[i].w;
dfs(v,fa);
}
}
ll res0,res1,res2;
//划分树;
void work(int zong,int u){
memset(vis,0,sizeof(vis));
vv.clear();
rt=u;
ans=zong;
get_rt(u,zong);
flag[rt]=1;
d[rt]=0;
memset(vis,0,sizeof(vis));
vis[rt]=1;
ll sum0=0,sum1=0,sum2=0;
ll numz0=0,numz1=0,numz2=0;//总的路径数量;
for(int i=head[rt];i!=-1;i=edge[i].next){
s0=s1=s2=n0=n1=n2=0;
int v=edge[i].v;
if(vis[v]||flag[v]) continue;
d[v]=0+edge[i].w;
dfs(v,v);
in.s0=s0,in.s1=s1,in.s2=s2,in.n0=n0,in.n1=n1,in.n2=n2;
vv.push_back(in);
sum0+=s0,sum1+=s1,sum2+=s2;
sum0%=mod,sum1%=mod,sum2%=mod;
numz0+=n0,numz1+=n1,numz2+=n2;
}
for(int i=0;i<vv.size();++i){
s0=vv[i].s0;//0
s1=vv[i].s1;//1
s2=vv[i].s2;//2
n0=vv[i].n0;//0路径数量;
n1=vv[i].n1;//1路径数量;
n2=vv[i].n2;//2路径数量;
if(n0&&numz0-n0) res0=(res0+s0*(numz0-n0)+n0*(sum0-s0))%mod;
if(n1&&numz2-n2) res0=(res0+s1*(numz2-n2)+n1*(sum2-s2))%mod;
if(n2&&numz1-n1) res0=(res0+s2*(numz1-n1)+n2*(sum1-s1))%mod;
if(n0&&numz1-n1) res1=(res1+s0*(numz1-n1)+n0*(sum1-s1))%mod;
if(n1&&numz0-n0) res1=(res1+s1*(numz0-n0)+n1*(sum0-s0))%mod;
if(n2&&numz2-n2) res1=(res1+s2*(numz2-n2)+n2*(sum2-s2))%mod;
if(n0&&numz2-n2) res2=(res2+s0*(numz2-n2)+n0*(sum2-s2))%mod;
if(n2&&numz0-n0) res2=(res2+s2*(numz0-n0)+n2*(sum0-s0))%mod;
if(n1&&numz1-n1) res2=(res2+s1*(numz1-n1)+n1*(sum1-s1))%mod;
if(n0) res0=(res0+s0*2)%mod;
if(n1) res1=(res1+s1*2)%mod;
if(n2) res2=(res2+s2*2)%mod;
}
/*划分子树,求第二种路径*/
int now=rt;
for(int i=head[now];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(flag[v]) continue;
work(size1[v],v);
}
}
void solve(){
init();
int u,v,w;
for(int i=1;i<n;++i){
scanf("%d%d%d",&u,&v,&w);
++u,++v;
add(u,v,w);
add(v,u,w);
}
work(n,1);
printf("%lld %lld %lld\n",res0,res1,res2);
}
int main(){
while(scanf("%d",&n)!=EOF){
res0=res1=res2=0;
solve();
}
return 0;
}