Fish eating fruit 点分治

树上任意两点之间的路径按照模 3 为 012 分类，将两点间距离加和（边权累和）  ，乘 2 即为答案。 

点分治模板题

路径长度乘路径贡献即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e5+6;
ll mod=1e9+7;
int n,m,head[N],pos,siz[N],siz_tree,x,y,z,vis[N],root,maxson[N];
ll ans[3],dis[N],cnt[N];
struct Edge{int to,nex,v;}edge[N<<1];
void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;}

void getroot(int x,int fa)
{
    siz[x]=1;maxson[x]=0;
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(vis[v]||v==fa)continue;
        getroot(v,x);siz[x]+=siz[v];
        maxson[x]=max(maxson[x],siz[v]);
    }
    maxson[x]=max(maxson[x],siz_tree-siz[x]);
    if(maxson[x]<maxson[root])root=x;
}
void getdis(int x ,int fa,int nowdis)
{
    cnt[nowdis%3]++;
    dis[nowdis%3]=(dis[nowdis%3]+nowdis);
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==fa||vis[v])continue;
        getdis(v,x,nowdis+edge[i].v);
    }
}

void calc(int x,int d,int flag)
{
    dis[0]=dis[1]=dis[2]=0;
    cnt[0]=cnt[1]=cnt[2]=0;
    getdis(x,0,d);
    
    for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)
    {
        ans[(i+j)%3]=(mod+ans[(i+j)%3]+(flag*(dis[i]*cnt[j]+dis[j]*cnt[i]))%mod)%mod;
    }
}
void solve(int x)
{
    calc(x,0,1);
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(vis[v])continue;
        calc(v,edge[i].v,-1);
        root=0;
        siz_tree=siz[v];
        getroot(v,x);
        solve(root);
    }
}
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),x++,y++,add(x,y,z),add(y,x,z);
        siz_tree=maxson[0]=n;
        root=0;
        getroot(1,0);
        solve(root);
        printf("%lld %lld %lld
",ans[0],ans[1],ans[2]);
        pos=ans[0]=ans[1]=ans[2]=0;
        for(int i=1;i<=n;i++)maxson[i]=0,head[i]=vis[i]=0;
    }
}