1 条题解
-
0
#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
- 上传者