// INOI20_sumtree
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const int MAXN = 200100;
const int MAXF = 500100;
const int LOGN = 25;
inline int poww(int a, int b)
{
int res = 1;
for (; b; a = (ll)a * a % mod, b /= 2) if (b & 1) res = (ll)res * a % mod;
return res;
}
int n, rt, q;
vector<int> adj[MAXN];
int bad, ans;
int sttime[MAXN], fntime[MAXN], timer, h[MAXN];
int lbl[MAXN], val[MAXN], cnt[MAXN];
int lpar[LOGN][MAXN];
int fact[MAXF], finv[MAXF];
inline int comb(int n, int k)
{
return (fact[n] * (ll)finv[k] % mod) * finv[n - k] % mod;
}
void dfs1(int v)
{
sttime[v] = timer++;
for (int u : adj[v]) if (u != lpar[0][v])
{
lpar[0][u] = v;
h[u] = h[v] + 1, dfs1(u);
}
fntime[v] = timer;
}
struct FEN
{
ll fen[MAXN];
inline void addind(int i, ll x)
{
for (i++; i < MAXN; i += i & -i) fen[i] += x;
}
inline ll pget(int i)
{
ll res = 0;
for (i++; i > 0; i -= i & -i) res += fen[i];
return res;
}
inline ll get(int l, int r)
{
if (l > r) return 0;
return pget(r) - pget(l - 1);
}
inline void add(int l, int r, ll x)
{
addind(l, x);
addind(r + 1, -x);
}
} valfen, ancfen;
struct node
{
int mn, mincnt, lz = -1;
};
struct SEG
{
node seg[4 * MAXN];
inline node mrg(const node &lc, const node &rc)
{
node res;
res.mn = min(lc.mn, rc.mn);
res.mincnt = 0;
if (lc.mn == res.mn) res.mincnt += lc.mincnt;
if (rc.mn == res.mn) res.mincnt += rc.mincnt;
return res;
}
inline void pushdown(int v)
{
if (seg[v].lz == -1) return;
FOR(t, 2 * v, 2 * v + 2)
{
if (seg[t].mn == seg[v].mn) seg[t].mn = seg[t].lz = seg[v].lz;
}
seg[v].lz = -1;
}
void build(int v = 1, int l = 0, int r = n - 1)
{
if (l == r)
{
seg[v] = {0, 1, -1};
return;
}
int mid = (r + l) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
seg[v].lz = -1;
}
void rset(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
if (l > R || r < L) return;
if (l >= L && r <= R)
{
seg[v].mn = seg[v].lz = x;
return;
}
int mid = (r + l) / 2;
pushdown(v);
rset(L, R, x, 2 * v, l, mid);
rset(L, R, x, 2 * v + 1, mid + 1, r);
seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
}
node getmin(int L, int R, int v = 1, int l = 0, int r = n - 1)
{
if (l > R || r < L) return {INF, 0, 0};
if (l >= L && r <= R) return seg[v];
int mid = (r + l) / 2;
pushdown(v);
return mrg(getmin(L, R, 2 * v, l, mid), getmin(L, R, 2 * v + 1, mid + 1, r));
}
} seg;
inline int getpar(int x, int d)
{
FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
return x;
}
inline void addans(int i)
{
if (val[i] < 0) bad++;
else ans = (ll)ans * comb(val[i] + cnt[i] - 1, cnt[i] - 1) % mod;
}
inline void remans(int i)
{
if (val[i] < 0) bad--;
else ans = (ll)ans * poww(comb(val[i] + cnt[i] - 1, cnt[i] - 1), mod - 2) % mod;
}
inline void updateval(int v)
{
ll nw = lbl[v] - valfen.get(sttime[v] + 1, fntime[v] - 1);
valfen.addind(sttime[v], nw - val[v]);
val[v] = nw;
}
inline int findanc(int v)
{
int l = 0, r = h[v] + 1;
int cur = ancfen.pget(sttime[v]);
while (r - l > 1)
{
int mid = (r + l) / 2;
int x = getpar(v, mid);
if (ancfen.pget(sttime[x]) == cur) l = mid;
else r = mid;
}
return getpar(v, l);
}
int32_t main(void)
{
fast_io;
fact[0] = 1;
FOR(i, 1, MAXF) fact[i] = fact[i - 1] * (ll)i % mod;
finv[MAXF - 1] = poww(fact[MAXF - 1], mod - 2);
for (int i = MAXF - 2; i >= 0; i--) finv[i] = (ll)finv[i + 1] * (i + 1) % mod;
cin >> n >> rt;
FOR(i, 0, n - 1)
{
int x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs1(1);
FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];
ans = comb(n + rt - 1, n - 1);
cout << ans << endl;
ancfen.add(0, n - 1, 1);
lbl[1] = val[1] = rt;
cnt[1] = n;
seg.build();
cin >> q;
while (q--)
{
int op, v;
cin >> op >> v;
if (op == 1) // add
{
int x;
cin >> x;
lbl[v] = x;
// update anc
int l = findanc(v);
ancfen.add(sttime[v], fntime[v] - 1, 1);
remans(l);
// update cnt
int c = seg.getmin(sttime[v], fntime[v] - 1).mincnt;
seg.rset(sttime[v], fntime[v] - 1, sttime[v]);
cnt[l] -= c;
cnt[v] += c;
// update val
updateval(v);
updateval(l);
addans(v);
addans(l);
}
else // rem
{
ancfen.add(sttime[v], fntime[v] - 1, -1);
int l = findanc(v);
remans(l);
remans(v);
int c = seg.getmin(sttime[v], fntime[v] - 1).mincnt;
seg.rset(sttime[v], fntime[v] - 1, sttime[l]);
cnt[l] += c;
cnt[v] = 0;
valfen.addind(sttime[v], -val[v]);
lbl[v] = val[v] = 0;
updateval(l);
addans(l);
}
ans = (mod + ans % mod) % mod;
if (bad) cout << "0\n";
else cout << ans << endl;
}
return 0;
}
Compilation message
Main.cpp: In member function 'void SEG::build(int, int, int)':
Main.cpp:125:22: error: no match for 'operator=' (operand types are 'node' and '<brace-enclosed initializer list>')
125 | seg[v] = {0, 1, -1};
| ^
Main.cpp:92:8: note: candidate: 'node& node::operator=(const node&)'
92 | struct node
| ^~~~
Main.cpp:92:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const node&'
Main.cpp:92:8: note: candidate: 'node& node::operator=(node&&)'
Main.cpp:92:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'node&&'
Main.cpp: In member function 'node SEG::getmin(int, int, int, int, int)':
Main.cpp:152:40: error: could not convert '{INF, 0, 0}' from '<brace-enclosed initializer list>' to 'node'
152 | if (l > R || r < L) return {INF, 0, 0};
| ^
| |
| <brace-enclosed initializer list>
