Submission #999163

#	Time	Username	Problem	Language	Result	Execution time	Memory
999163		vjudge1	Sumtree (INOI20_sumtree)	C++17	10 / 100	357 ms	115792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
const int N = 4e5+10;
const int MAXNC=5e5+10;
const int LG = 20;
vector<int> g[N];
int tin[N], tout[N], tim=0;
int up[N][LG], tags[N];
long long fact[MAXNC];
int depth[N], sz[N], used[N];

namespace BIT {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
namespace BIT2 {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
namespace BIT3 {
  int fen[N];
  void add(int at, int vl) {
    at++;
    while(at < N) {
      fen[at] += vl;
      at+=at&(-at);
    }
  }
  int query(int at) {
    at++;
    int res=0;
    while(at) {
      res+=fen[at];
      at-=at&(-at);
    }
    return res;
  }
};
void change(int x, int vl) {
  BIT::add(tin[x], vl);
  BIT::add(tout[x], -vl);
}
int query(int anc, int ch) {
  return BIT::query(tin[ch])-BIT::query(tin[anc]);
}
int query2(int l, int r) {
  if(l>r)return 0;
  if(l == 0)return BIT2::query(r);
  return BIT2::query(r)-BIT2::query(l-1);
}

int query3(int l, int r) {
  if(l>r)return 0;
  if(l == 0)return BIT3::query(r);
  return BIT3::query(r)-BIT3::query(l-1);
}

long long binpow(long long a, long long b) {
  long long res = 1;
  while(b) {
    if(b&1) {
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    b>>=1;
  }
  return res;
}
long long ncr(long long nn, long long rr) {
  if(rr > nn)return 0;
  if(rr < 0)return 0;
  long long res = fact[nn];
  res = (res*binpow(fact[rr], mod-2))%mod;
  res = (res*binpow(fact[nn-rr], mod-2))%mod;
  return res;
}
void dfs(int at, int p) {
  sz[at]=1;
  up[at][0] = p;
  for(int i = 1;i<LG;i++)up[at][i] = up[up[at][i-1]][i-1];
  tin[at] = tim++;
  for(int to:g[at]) {
    if(to == p)continue;
    depth[to]=depth[at]+1;
    dfs(to, at);
    sz[at]+=sz[to];
  }
  tout[at] = tim++;
}

int findroot(int at) {
  for(int i = LG-1;i>=0;i--) {
    if(up[at][i] != 0 and query(up[at][i], at) == depth[at]-depth[up[at][i]]) {
      at = up[at][i];
    }
  }
  return at;
}

struct ANS {
  long long mult = 1;
  long long zero = 0;
  void add(long long vl) {
    if(vl == 0)
      zero++;
    else
      mult = (mult*vl)%mod;
  }
  void del(long long vl) {
    if(vl == 0) {
      zero--;
    }
    else {
      mult = (mult*binpow(vl, mod-2))%mod;
    }
  }
  long long get() {
    if(zero>0)return 0;
    return mult;
  }

};
int main () {
  cin.tie(0)->sync_with_stdio(0);
  fact[0] = 1;
  for(int i = 1;i<MAXNC;i++)fact[i] = (fact[i-1]*i)%mod;
  int n, r;
  cin >> n >> r;
  for(int i = 1;i<n;i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  tags[1] = r;
  used[1] = 1;
  for(int i = 2;i<=n;i++)change(i, 1);
  for(int i = 1;i<=n;i++) {
    BIT2::add(tin[i], 1);
  }
  BIT3::add(tin[1], r);
  BIT3::add(tout[1], -r);
  ANS ans;
  ans.add(ncr(n+r-1, r));
  cout << ans.get() << "\n";
  int q;
  cin >> q;
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
      tags[u]=v;
      long long rr = findroot(u);
      // delete answer of root
      {
        long long szz = query2(tin[rr], tout[rr]);
        long long tagsm = query3(tin[rr], tout[rr]);
        long long tmp = tags[rr]-tagsm;
        ans.del(ncr(szz+tmp-1, tmp));
      }
      // add answer of u
      {
        long long szz = query2(tin[u], tout[u]);
        long long tagsm = query3(tin[u], tout[u]);
        long long tmp = v-tagsm;
        ans.add(ncr(szz+tmp-1, tmp));
        // modify BITS of u
        BIT2::add(tin[up[u][0]], -szz);
        BIT3::add(tin[up[u][0]], -tmp);
        BIT3::add(tout[up[u][0]], tmp);
      }
      {
        long long szz = query2(tin[rr], tout[rr]);
        long long tagsm = query3(tin[rr], tout[rr]);
        long long tmp = tags[rr]-tagsm;
        ans.add(ncr(szz+tmp-1, tmp));
      }
      change(u, 0);
    }
    else {
      int u;
      cin >> u;
      long long rr = findroot(u);
      // delete answer of root
      {
        long long szz = query2(tin[rr], tout[rr]);
        long long tagsm = query3(tin[rr], tout[rr]);
        long long tmp = tags[rr]-tagsm;
        ans.del(ncr(szz+tmp-1, tmp));
      }
      {
        long long szz = query2(tin[u], tout[u]);
        long long tagsm = query3(tin[u], tout[u]);
        long long tmp = tags[u]-tagsm;
        ans.del(ncr(szz+tmp-1, tmp));
        BIT2::add(tin[up[u][0]], szz);
        BIT3::add(tin[up[u][0]], tmp);
        BIT3::add(tout[up[u][0]], -tmp);
      }
      {
        long long szz = query2(tin[rr], tout[rr]);
        long long tagsm = query3(tin[rr], tout[rr]);
        long long tmp = tags[rr]-tagsm;
        ans.add(ncr(szz+tmp-1, tmp));
      }
      tags[u]=-1;

    }
    cout << ans.get() << "\n";
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30