1 条题解

  • 0
    @ 2026-8-9 11:30:50
    #include <bits/stdc++.h>
    #define int long long
    #define mk make_pair
    #define PII pair<int,int>
    #define FOR(i,j,k) for(int i=(j);i<=(k);++i)
    #define ROF(i,j,k) for(int i=(j);i>=(k);--i)
    #define FOI(a,b) for(auto a : b)
    #define wh while
    #define inf 0x3f3f3f3f3f3f3f3f
    #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define snd second
    #define fst first
    #define pb push_back
    #define CI const int
    #define NP namespace
    using NP std;
    int quickpow(int a,int b)
    {
    	int ans=1;
    	wh(b)
    	{
    		if(b&1)ans=ans*a;
            a=a*a;
    		b>>=1;
    	}
    	return ans;
    }
    CI MAXN=5e5+5,MOD=1e9+7;
    int ans,sz[MAXN],n;
    vector<int> g[MAXN];
    void dfs(int u,int fa)
    {
    	sz[u]=1;
    	FOI(s,g[u])
    	{
    		if(s==fa)continue;
    		dfs(s,u);
    		sz[u]+=sz[s];
    	}
    	int sum=n-sz[u]+1,now=n-sz[u],c=0;
    	FOI(s,g[u])
    	{
    		if(s==fa)continue;
    		sum=(sum*(sz[s]+1))%MOD;
    		c=(c+(now*sz[s]))%MOD;
    		now=(now+sz[s])%MOD;
    	}
    	ans=(ans+(sum-n-c))%MOD;
    }
    signed main(void)
    {
    
        freopen("star.in","r",stdin);
        freopen("star.out","w",stdout);
    	IOS
    	cin>>n;
    	FOR(i,2,n)
    	{
    		int u,v;
    		cin>>u>>v;
    		g[u].pb(v);
    		g[v].pb(u);
    	}
    	dfs(1,-1);
    	cout<<ans; 
        return false;
    }
    
    
    
    
    
    
    
    
    
    • 1

    信息

    ID
    7132
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    (无)
    递交数
    6
    已通过
    2
    上传者