吉首大学2019年程序设计竞赛（重现赛） J 滑稽树下你和我（递归）

￡神魔★判官ぃ 2021-11-22 04:46 141阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/992/J][https_ac.nowcoder.com_acm_contest_992_J]  
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 32768K，其他语言65536K  
64bit IO Format: %lld

## 题目描述 ##

红红和蓝蓝是随机降生在苹果树上的苹果仙灵，现在红线仙想估测他们的CP系数，并决定是否使他们成为一对CP。

给出n个结点n-1条边的树，节点编号为1到n,定义distance(i,j)为i与j的树上距离。

CP系数是指所有红红和蓝蓝在不同位置i,j的distance(i,j)之和。

即  ∑n−1i=1∑nj=i\+1distance(i,j)∑i=1n−1∑j=i+1ndistance(i,j)。

求红红和蓝蓝的CP系数，对10 9\+7取模。

## 输入描述: ##

第一行一个整数n（ 1 < n <= 10 5 ),表示树的结点个数。

随后n-1行，每行三个整数a,b,c ( 1 <= a,b <= n ),( 0 <= c <= 10 9 )，表示结点a,b之间有一条权值为c的边,( a  ≠≠ b )。

## 输出描述: ##

一行一个整数，表示CP系数对10

+7取模的结果。

示例1

## 输入 ##

复制

4
    1 2 1
    2 3 1
    2 4 1

## 输出 ##

复制

## 说明 ##

distance(1,2)=1

distance(1,3)=2

distance(1,4)=2

distance(2,3)=1

distance(2,4)=1

distance(3,4)=2

CP系数=(1+2+2+1+1+2)%(10 9\+7)=9

解题思路：很简单求树上任意两点的距离之和，每条边的贡献等于它两边的点数相乘再乘以边权即可，答案累加一下就可以了，递归处理下就可以了。

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod=1e9+7;
    const int  maxn=1e5+7;
    ll ans;
    struct node{
        int v,next; ll w;
    }edge[maxn*2];
    int n,tot,d[maxn],head[maxn];
    void add(int u,int v,ll w){
        edge[tot].v=v;
        edge[tot].w=w;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dfs(int u,int fa){
        d[u]=1;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            ll w=edge[i].w;
            if(v!=fa){
                dfs(v,u);
                d[u]+=d[v];
                ans=(ans+d[v]*(n-d[v])%mod*w%mod)%mod;
            }
        }
    }
    int main(){
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++){
            int u,v; ll w;
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0);
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/zjl192628928/p/11187659.html

[https_ac.nowcoder.com_acm_contest_992_J]: https://ac.nowcoder.com/acm/contest/992/J