fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll NINF = (ll)-4e18;
  5. const int MOD = 1'000'000'007;
  6.  
  7. struct VC { ll v; int c; VC(ll V=NINF,int C=0):v(V),c(C){} };
  8. inline VC mx(const VC&a,const VC&b){ if(a.v>b.v) return a; if(b.v>a.v) return b; return VC(a.v,(a.c+b.c)%MOD); }
  9. inline VC add(const VC&a,const VC&b){ if(!a.c||!b.c) return VC(NINF,0); return VC(a.v+b.v,(int)(1LL*a.c*b.c%MOD)); }
  10.  
  11. struct M {
  12.   VC a[2][2];
  13.   M(){ a[0][0]=a[0][1]=a[1][0]=a[1][1]=VC(NINF,0); }
  14.   static M I(){ M x; x.a[0][0]=VC(0,1); x.a[1][1]=VC(0,1); return x; }
  15. };
  16. M mulm(const M&A,const M&B){
  17.   M C;
  18.   for(int i=0;i<2;i++) for(int j=0;j<2;j++){
  19.     VC t(NINF,0);
  20.     for(int k=0;k<2;k++) t=mx(t,add(A.a[i][k],B.a[k][j]));
  21.     C.a[i][j]=t;
  22.   }
  23.   return C;
  24. }
  25. M mor(const M&A,const M&B){
  26.   M C;
  27.   for(int i=0;i<2;i++) for(int j=0;j<2;j++) C.a[i][j]=mx(A.a[i][j],B.a[i][j]);
  28.   return C;
  29. }
  30. M mpow(M b, long long e){
  31.   M r=M::I();
  32.   while(e){ if(e&1) r=mulm(r,b); b=mulm(b,b); e>>=1; }
  33.   return r;
  34. }
  35. struct V2 { VC x[2]; V2(){ x[0]=x[1]=VC(NINF,0); } static V2 sN(int er){ V2 v; v.x[0]=VC(0,1); v.x[1]=VC(-er,1); return v; } static V2 sR(int er,int ex){ V2 v; v.x[0]=VC(0,1); v.x[1]=VC(-er-ex,1); return v; } };
  36. V2 mulvm(const V2&v,const M&A){
  37.   V2 y;
  38.   for(int j=0;j<2;j++){ VC t(NINF,0); for(int k=0;k<2;k++) t=mx(t,add(v.x[k],A.a[k][j])); y.x[j]=t; }
  39.   return y;
  40. }
  41. VC fin(const V2&v,int el){ return mx(add(v.x[0],VC(0,1)), add(v.x[1],VC(1-el,1))); }
  42.  
  43. int n; long long d;
  44. vector<vector<int>> g;
  45. vector<int> par; vector<vector<int>> ch; vector<int> ord;
  46. vector<int> A,B,S,UA,UB; vector<char> UH,ess;
  47.  
  48. void build(int s=0){
  49.   par.assign(n,-1); ch.assign(n,{}); ord.clear();
  50.   vector<int> st={s}; par[s]=-2;
  51.   while(!st.empty()){ int u=st.back(); st.pop_back(); ord.push_back(u); for(int v:g[u]) if(par[v]==-1){ par[v]=u; st.push_back(v);} }
  52.   par[s]=-1; for(int v=0;v<n;v++) if(par[v]!=-1) ch[par[v]].push_back(v);
  53. }
  54. void down(){
  55.   A.assign(n,0); B.assign(n,0); S.assign(n,0);
  56.   for(int i=n-1;i>=0;i--){
  57.     int u=ord[i], sum=0, best=INT_MIN/4;
  58.     for(int v:ch[u]){ sum+=A[v]; best=max(best, B[v]-A[v]); }
  59.     S[u]=sum; B[u]=sum; A[u]=(best<=INT_MIN/8?sum:max(sum,sum+1+best));
  60.   }
  61. }
  62. void up(){
  63.   UA.assign(n,0); UB.assign(n,0); UH.assign(n,0); UH[0]=0;
  64.   vector<vector<int>> pre(n),suf(n);
  65.   for(int u:ord){
  66.     int k=ch[u].size();
  67.     pre[u].assign(k+1,INT_MIN/4);
  68.     for(int i=0;i<k;i++){ int v=ch[u][i]; pre[u][i+1]=max(pre[u][i], B[v]-A[v]); }
  69.     suf[u].assign(k+1,INT_MIN/4);
  70.     for(int i=k-1;i>=0;i--){ int v=ch[u][i]; suf[u][i]=max(suf[u][i+1], B[v]-A[v]); }
  71.   }
  72.   for(int u:ord){
  73.     int k=ch[u].size();
  74.     for(int i=0;i<k;i++){
  75.       int v=ch[u][i];
  76.       int Sex=UA[u]+(S[u]-A[v]);
  77.       int best=max(pre[u][i],suf[u][i+1]);
  78.       if(UH[u]) best=max(best,UB[u]-UA[u]);
  79.       UB[v]=Sex; UA[v]=(best<=INT_MIN/8?Sex:max(Sex,Sex+1+best)); UH[v]=1;
  80.     }
  81.   }
  82. }
  83. void compE(){
  84.   ess.assign(n,0);
  85.   int M=A[0];
  86.   for(int u=0;u<n;u++){ int rem=UA[u]+S[u]; ess[u]=(M>rem); }
  87. }
  88.  
  89. vector<char> inD,inA; vector<int> cid, Dc, Ac; vector<char> tight;
  90. void GE(){
  91.   inD.assign(n,0); for(int u=0;u<n;u++) inD[u]=!ess[u];
  92.   inA.assign(n,0); for(int u=0;u<n;u++) if(inD[u]) for(int v:g[u]) inA[v]=1;
  93.   cid.assign(n,-1); Dc.clear(); Ac.clear();
  94.   vector<int> vis(n,0); int id=0;
  95.   for(int u=0;u<n;u++){
  96.     if(vis[u] || !(inD[u]||inA[u])) continue;
  97.     queue<int> q; q.push(u); vis[u]=1; int dcnt=0, acnt=0; vector<int> nodes;
  98.     while(!q.empty()){
  99.       int x=q.front(); q.pop(); nodes.push_back(x);
  100.       if(inD[x]) dcnt++; else if(inA[x]) acnt++;
  101.       for(int y:g[x]){
  102.         if(!((inD[x]&&inA[y])||(inA[x]&&inD[y]))) continue;
  103.         if(!vis[y]){ vis[y]=1; q.push(y); }
  104.       }
  105.     }
  106.     for(int x:nodes) if(inD[x]) cid[x]=id;
  107.     Dc.push_back(dcnt); Ac.push_back(acnt); id++;
  108.   }
  109.   tight.assign(id,0);
  110.   for(int i=0;i<id;i++) tight[i]=(Dc[i]-Ac[i]==1);
  111. }
  112.  
  113. struct P { long long ee_same=0,ee_diff=0,enL=0,enR=0,nn_same=0,nn_tight=0,nn_other=0; };
  114. P cntPairs(){
  115.   long long E=0, NE=0; for(int u=0;u<n;u++) (ess[u]?E:NE)++;
  116.   long long T=0,S2=0; for(size_t i=0;i<Dc.size();i++) if(tight[i]){ T+=Dc[i]; S2+=1LL*Dc[i]*Dc[i]; }
  117.   P p;
  118.   p.ee_same = E;
  119.   p.ee_diff = E*E - E;
  120.   p.enL = E*NE;
  121.   p.enR = NE*E;
  122.   p.nn_same = NE;
  123.   p.nn_tight = S2 - T;
  124.   p.nn_other = NE*NE - p.nn_same - p.nn_tight;
  125.   return p;
  126. }
  127.  
  128. M mat(int eL,int eR,int ex,int forbd){
  129.   M T;
  130.   T.a[0][0]=VC(0,1);
  131.   T.a[0][1]=VC(-eR,1);
  132.   T.a[1][0]=VC(1-eL,1);
  133.   if(forbd) T.a[1][1]=VC(NINF,0);
  134.   else T.a[1][1]=VC(1-eL-eR-ex,1);
  135.   return T;
  136. }
  137. M agg1(const vector<pair<M,ll>>& lst){
  138.   M R;
  139.   for(auto &t:lst){
  140.     M X=t.first; ll cnt=t.second%MOD;
  141.     if(!cnt) continue;
  142.     for(int i=0;i<2;i++) for(int j=0;j<2;j++){ if(X.a[i][j].c) X.a[i][j].c=(int)cnt; }
  143.     R=mor(R,X);
  144.   }
  145.   return R;
  146. }
  147.  
  148. struct EC { int r[2]; int exr; int l[2]; };
  149. EC ends(int s){
  150.   int E=0,NE=0; for(int u=0;u<n;u++) (ess[u]?E:NE)++;
  151.   EC e{}; e.r[1]=E%MOD; e.r[0]=NE%MOD; e.l[1]=E%MOD; e.l[0]=NE%MOD;
  152.   if(ess[s]) e.exr=0;
  153.   else{
  154.     int id=cid[s];
  155.     if(id>=0 && tight[id]) e.exr = Dc[id]%MOD;
  156.     else e.exr=0;
  157.   }
  158.   return e;
  159. }
  160.  
  161. int main(){
  162.   ios::sync_with_stdio(false);
  163.   cin.tie(nullptr);
  164.   cin>>n>>d;
  165.   g.assign(n,{});
  166.   for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; --u;--v; g[u].push_back(v); g[v].push_back(u); }
  167.   build(0); down(); up(); compE(); GE();
  168.  
  169.   P p = cntPairs();
  170.   vector<pair<M,ll>> lst;
  171.   lst.push_back({mat(1,1,0,1), p.ee_same});
  172.   lst.push_back({mat(1,1,0,0), p.ee_diff});
  173.   lst.push_back({mat(1,0,0,0), p.enL});
  174.   lst.push_back({mat(0,1,0,0), p.enR});
  175.   lst.push_back({mat(0,0,0,1), p.nn_same});
  176.   lst.push_back({mat(0,0,1,0), p.nn_tight});
  177.   lst.push_back({mat(0,0,0,0), p.nn_other});
  178.   M step = agg1(lst);
  179.   M mid = (d>=2? mpow(step,d-1): M::I());
  180.  
  181.   EC e = ends(0);
  182.   ll ans = 0;
  183.   for(int er=0;er<=1;er++){
  184.     V2 vN = V2::sN(er);
  185.     V2 vR0 = V2::sR(er,0);
  186.     V2 vR1 = V2::sR(er,1);
  187.     V2 tN = mulvm(vN,mid), tR0 = mulvm(vR0,mid), tR1 = mulvm(vR1,mid);
  188.     for(int el=0;el<=1;el++){
  189.       VC VN = fin(tN,el), VR0 = fin(tR0,el), VR1 = fin(tR1,el);
  190.       if(ess[0]){ if(VR0.c) VR0.v-=1; if(VR1.c) VR1.v-=1; }
  191.       int cntR = e.r[er], cntRe = (er==0? e.exr:0), cntL = e.l[el];
  192.       if(VN.v>VR0.v){ ll add = 1LL*((cntR - cntRe + MOD)%MOD)*cntL%MOD; add = add*VN.c%MOD; ans=(ans+add)%MOD; }
  193.       if(cntRe && VN.v>VR1.v){ ll add = 1LL*cntRe*cntL%MOD; add = add*VN.c%MOD; ans=(ans+add)%MOD; }
  194.     }
  195.   }
  196.   cout<<ans%MOD<<"\n";
  197.   return 0;
  198. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3 1
1 2
2 3
stdout
copy 
4
https://ideone.com/pIejvB
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!