oj.uz

Submission #999163

# Submission time Handle Problem Language Result Execution time Memory
999163 2024-06-15T07:35:52 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 357 ms 115792 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 58964 KB Output is correct
2 Correct 92 ms 58964 KB Output is correct
3 Correct 99 ms 58964 KB Output is correct
4 Correct 92 ms 58960 KB Output is correct
5 Correct 80 ms 55160 KB Output is correct
6 Correct 7 ms 26460 KB Output is correct
7 Correct 6 ms 26140 KB Output is correct
8 Correct 7 ms 26192 KB Output is correct
9 Correct 87 ms 51284 KB Output is correct
10 Correct 88 ms 51280 KB Output is correct
11 Correct 97 ms 51284 KB Output is correct
12 Correct 84 ms 50868 KB Output is correct
13 Correct 83 ms 57936 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 25948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 115792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 54356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 58964 KB Output is correct
2 Correct 92 ms 58964 KB Output is correct
3 Correct 99 ms 58964 KB Output is correct
4 Correct 92 ms 58960 KB Output is correct
5 Correct 80 ms 55160 KB Output is correct
6 Correct 7 ms 26460 KB Output is correct
7 Correct 6 ms 26140 KB Output is correct
8 Correct 7 ms 26192 KB Output is correct
9 Correct 87 ms 51284 KB Output is correct
10 Correct 88 ms 51280 KB Output is correct
11 Correct 97 ms 51284 KB Output is correct
12 Correct 84 ms 50868 KB Output is correct
13 Correct 83 ms 57936 KB Output is correct
14 Incorrect 5 ms 25948 KB Output isn't correct
15 Halted 0 ms 0 KB -