题:https://nanti.jisuanke.com/t/41403

题意：求任意俩点之间距离之和模3后的三个结果的总数（原距离之和）

第一种做法：

树形dp

 

#include
      
       using namespace std;#define pb push_backtypedef long long ll;const int M=1e4+4;const int mod=1e9+7;struct node{    int v;    ll w;};ll C[M][3],S[M][3],ans[M];//C[i][j]:表示以i为根，然后路径消耗取模后为j的路径数//S[i][j]:表示以i为根，路径消耗取模后为j的路径总消耗 vector
       
        e[M];;void dfs(int u,int f,ll pre){    C[u][0]=C[u][1]=C[u][2]=0;    S[u][0]=S[u][1]=S[u][2]=0;    int len=e[u].size();    for(int i=0;i
       
      

 第二种做法：

点分治

#include
      
       using namespace std;typedef long long ll;const int M=2e4+4;const ll mod=1e9+7;struct node{    int v,nextt;    ll w;}e[M<<1];ll sum[4],disnum[4],dissum[4];int head[M],vis[M],sz[M],maxv[M],tot,n,maxx,root;void addedge(int u,int v,ll w){    e[tot].v=v;    e[tot].nextt=head[u];    e[tot].w=w;    head[u]=tot++;}void dfssz(int u,int f){    maxv[u]=0;    sz[u]=1;    for(int i=head[u];~i;i=e[i].nextt){        int v=e[i].v;        if(v==f||vis[v])            continue;        dfssz(v,u);        sz[u]+=sz[v];        maxv[u]=max(maxv[u],sz[v]);    }}void dfsroot(int r,int u,int f){    maxv[u]=max(maxv[u],sz[r]-sz[u]);    if(maxx>maxv[u]){        maxx=maxv[u];        root=u;    }    for(int i=head[u];~i;i=e[i].nextt){        int v=e[i].v;        if(v==f||vis[v])            continue;        dfsroot(r,v,u);    }}void dfsdis(int u,int f,ll d){//    if(f!=-1&&d!=0)    disnum[d%3]++;    disnum[d%3]%=mod;    dissum[d%3]+=d;    dissum[d%3]%=mod;    for(int i=head[u];~i;i=e[i].nextt){        int v=e[i].v;        if(vis[v]||v==f)            continue;        dfsdis(v,u,(d+e[i].w)%mod);    }}void cal(int u,ll d,int flag){    for(int i=0;i<3;i++)        dissum[i]=disnum[i]=0;        dfsdis(u,-1,d);    for(int i=0;i<3;i++)        for(int j=0;j<3;j++){            int t=(i+j)%3;            sum[t]=(sum[t]+flag*((disnum[i]*dissum[j]%mod+disnum[j]*dissum[i]%mod)%mod)%mod+mod)%mod;        }}void solve(int u){    maxx=n;    dfssz(u,-1);    dfsroot(u,u,-1);    cal(root,0ll,1);//+    vis[root]=1;    for(int i=head[root];~i;i=e[i].nextt){        int v=e[i].v;        if(vis[v])            continue;        cal(v,e[i].w,-1);        solve(v);    }}int main(){    while(~scanf("%d",&n)){        sum[0]=sum[1]=sum[2]=0;        tot=0;        for(int i=0;i<=n;i++)            head[i]=-1,vis[i]=0;;        for(int i=1;i