吉首大学2019年程序设计竞赛（重现赛）-J（树形DP）

题目链接：https://ac.nowcoder.com/acm/contest/992/J

题意：题意很清晰，就是求任意两点距离的和，结果对1e9+7取模。

思路：裸的树形DP题，一条边的贡献值=这条边的权值×左端连接的顶点数×右端连接的顶点数，所以我们dfs算出点y的子树大小siz[y]，x为y的父结点，则x与y连线这条边的一端点的个数为siz[y]，另一端点的个数为n-siz[y] ，贡献值即为dis[x,y]*siz[y]*(n-siz[y])，注意取模。

AC代码：

#include<cstdio>

using namespace std;

typedef long long LL;

const int MOD=1e9+;

const int maxn=1e5+;

struct node{

    int v,w,nex;

}edge[maxn<<];

int n,cnt,head[maxn],siz[maxn];

LL ans;

void add(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void dfs(int x,int f){

    siz[x]=;

    for(int i=head[x];i;i=edge[i].nex){

        int y=edge[i].v;

        if(y==f) continue;

        dfs(y,x);

        siz[x]+=siz[y];

        ans+=1LL*edge[i].w*siz[y]%MOD*(n-siz[y])%MOD;

        ans%=MOD;

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<n;++i){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dfs(,);

    printf("%lld\n",ans);

    return ;

}