pastebin

pastebin

Paste Search Dynamic
Recent pastes
numstage
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define pb push_back
  5. #define pob pop_back
  6.  
  7. const ll mod = 1000000007;
  8. const int NAX = 200002;
  9. vector<int> g[NAX];
  10. vector<int> g2[NAX];
  11. int n;
  12. vector<ll> pw(NAX);
  13. vector<int> indeg(NAX);
  14. ll answer;
  15.  
  16. void dfs(int u, int pa){
  17.         for (int i=0; i<g[u].size(); i++){
  18.                 int v=g[u][i];
  19.                 if (v!=pa){
  20.                         dfs(v,u);
  21.                 }
  22.         }
  23.         if (u>1){
  24.                 g2[u].pb(pa);
  25.                 indeg[pa]++;
  26.         }
  27. }
  28.  
  29. void solve(){
  30.         cin>>n;
  31.         for (int i=1; i<=n; i++) g[i].clear(), g2[i].clear(), indeg[i]=0;
  32.         answer=0;
  33.        
  34.         for (int i=0; i<n-1; i++){
  35.                 int a,b; cin>>a>>b;
  36.                 g[a].pb(b);
  37.                 g[b].pb(a);
  38.         }
  39.         dfs(1,0);
  40.         vector<int> bfs;
  41.         for (int i=1; i<=n; i++){
  42.                 if (indeg[i]==0) bfs.pb(i);
  43.         }
  44.         vector<int> numstage;
  45.         while(!bfs.empty()){
  46.                 numstage.pb(bfs.size());
  47.                 vector<int> nvec;
  48.                 while(!bfs.empty()){
  49.                         int u=bfs.back();
  50.                         bfs.pob();
  51.                         for (int i=0; i<g2[u].size(); i++){
  52.                                 int v=g2[u][i];
  53.                                 indeg[v]--;
  54.                                 if (indeg[v]==0){
  55.                                         nvec.pb(v);
  56.                                 }
  57.                         }
  58.                 }
  59.                 bfs=nvec;
  60.         }
  61.         reverse(numstage.begin(),numstage.end());
  62.         int x=0;
  63.         for (int i=0; i<numstage.size(); i++){
  64.                 if (x>0) answer = (answer + (pw[n-x]*answer)%MOD )%MOD;
  65.                 answer = (answer + pw[n-numstage[i]])%MOD;
  66.                 x=x+numstage[i];
  67.         }
  68.        
  69.         cout<<answer<<'n';
  70. }
  71.  
  72. int main() {
  73.         ios::sync_with_stdio(0);
  74.         cin.tie(0);
  75.        
  76.         pw[0]=1;
  77.         for (int i=1; i<NAX; i++) pw[i]=(pw[i-1]*2)%MOD;
  78.        
  79.         int t; cin>>t;
  80.         while(t--) solve();
  81.        
  82.         return 0;
  83. }
Parsed in 0.010 seconds