oj.uz

Submission #999127

# Submission time Handle Problem Language Result Execution time Memory
999127 2024-06-15T07:03:21 Z vjudge1 Sumtree (INOI20_sumtree) C++17
10 / 100
 308 ms 51812 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], val[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);
  int vv[n+1];
  val[1] = r;
  used[1] = 1;
//  for(int i = 2;i<=n;i++)change(i, 1);
//  BIT3::update(tin[1], -n);
//  BIT3::update(tout[1], n);
  ANS ans;
  ans.add(ncr(n+r-1, r));
  cout << ans.get() << "\n";
//  for(int i = 1;i<=n;i++) {
//    assert(depth[i]*depth[i] <= n*n+10);
//  }
  int q;
  cin >> q;
  while(q--) {
    int t;
    cin >> t;
    if(t == 1) {
      int u, v;
      cin >> u >> v;
      val[u] += v; 
      vv[u]=v;
      used[u] = 1;
      int par = up[u][0];
      int rr = -1;
      while(1) {
        if(used[par] == 1) {
          ans.del(ncr(sz[par]+val[par]-1, val[par]));
        }
        sz[par] -= sz[u];
        val[par] -= v;
        if(used[par]==1){
          ans.add(ncr(sz[par]+val[par]-1, val[par]));
          break;
        }
        par=up[par][0];
      }
      ans.add(ncr(sz[u]+val[u]-1, val[u]));
    }
    else {
      int u;
      cin >> u;
      ans.del(ncr(sz[u]+val[u]-1, val[u]));
      used[u] = 0;
      val[u]-=vv[u];
      int par = up[u][0];
      int rr = -1;
      while(1) {
        if(used[par] == 1) {
          ans.del(ncr(sz[par]+val[par]-1, val[par]));
        }
        sz[par] += sz[u];
        val[par] += vv[u];
        if(used[par]==1){
          ans.add(ncr(sz[par]+val[par]-1, val[par]));
          break;
        }
        par=up[par][0];
      }
    }
    cout << ans.get() << "\n";
  }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:191:11: warning: unused variable 'rr' [-Wunused-variable]
  191 |       int rr = -1;
      |           ^~
Main.cpp:213:11: warning: unused variable 'rr' [-Wunused-variable]
  213 |       int rr = -1;
      |           ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 51792 KB Output is correct
2 Correct 78 ms 51800 KB Output is correct
3 Correct 74 ms 51792 KB Output is correct
4 Correct 74 ms 51812 KB Output is correct
5 Correct 61 ms 47700 KB Output is correct
6 Correct 7 ms 19548 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 80 ms 44928 KB Output is correct
10 Correct 71 ms 44740 KB Output is correct
11 Correct 68 ms 44880 KB Output is correct
12 Correct 68 ms 44444 KB Output is correct
13 Correct 64 ms 48720 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 51792 KB Output is correct
2 Correct 78 ms 51800 KB Output is correct
3 Correct 74 ms 51792 KB Output is correct
4 Correct 74 ms 51812 KB Output is correct
5 Correct 61 ms 47700 KB Output is correct
6 Correct 7 ms 19548 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 80 ms 44928 KB Output is correct
10 Correct 71 ms 44740 KB Output is correct
11 Correct 68 ms 44880 KB Output is correct
12 Correct 68 ms 44444 KB Output is correct
13 Correct 64 ms 48720 KB Output is correct
14 Incorrect 5 ms 19292 KB Output isn't correct
15 Halted 0 ms 0 KB -