/// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define FOR(i,a) for(int i = 0; i < a; i++)
#define se second
#define fi first
#define sz(x) (int)x.size()
#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define mp make_pair
typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod = 1'000'000'007;
const int N = 200'000 + 5;
const int Z = 2*500'000 + 5;
ll F[Z], _F[Z], ans;
int n, r, q, H[N], S[N], dad[N], st[N], en[N], R[N], B[N], tag[N], timer = 1, p = 0, cnt = 0;
set<pii> X[N];
vector<int> G[N];
inline ll Pow(ll a, int b)
{
ll res = 1LL;
while(b)
{
if(b&1)res = res*a%mod;
b >>= 1;
a = a*a%mod;
}
return res;
}
inline ll inv(int x){return Pow(x,mod-2);}
inline ll C(int x, int y)
{
return -1;
if(x > y || x < 0)return 0;
return F[y]*_F[x]%mod*_F[y-x]%mod;
}
struct fen
{
int G[N];
fen(){memset(G,0,sizeof(G));}
inline void inc(int p, int x)
{
while(p < N)
{
G[p] += x;
p += p&-p;
}
}
inline int get(int p)
{
int s = 0;
while(p)
{
s += G[p];
p -= p&-p;
}
return s;
}
}tags, Free;
int dfs_s(int v, int d, int h)
{
st[v] = timer++;
H[v] = h;
dad[v] = d;
S[v] = 1;
for(auto u: G[v])if(u != d)S[v] += dfs_s(u,v,h+1);
en[v] = timer;
return S[v];
}
void dfs_hld(int v, int top, int nam)
{
R[v] = nam;
B[v] = top;
pii MAX = mp(-1,-2);
for(auto u: G[v])if(u != dad[v])MAX = max(MAX,mp(S[u],u));
for(auto u: G[v])if(u != dad[v])
{
if(MAX.se == u)dfs_hld(u,top,nam);
else dfs_hld(u,u,p++);
}
}
inline int first_up(int v)
{
auto top = X[R[v]].upp(mp(H[v],v));
if(top == X[R[v]].begin())
{
v = dad[B[v]];
return first_up(v);
}
else
{
--top;
return (*top).se;
}
}
inline void upd(int v, int tg, int fs)
{
int nfs = S[v]-Free.get(en[v]-1)+Free.get(st[v]);
int ntg = tag[v]-tags.get(en[v]-1)+tags.get(st[v]);
if(C(ntg,nfs+ntg-1) == 0)cnt++;
else ans = ans*C(ntg,nfs+ntg-1)%mod;
nfs += fs;
ntg += tg;
if(C(ntg,nfs+ntg-1) == 0)cnt--;
else ans = ans*inv(C(ntg,nfs+ntg-1))%mod;
}
int main()
{
Fast
F[0] = 1;
for(ll i = 1; i < Z; i++)F[i] = i*F[i-1]%mod;
_F[Z-1] = inv(F[Z-1]);
for(ll i = Z-2; i >= 0; i--)_F[i] = (i+1LL)*_F[i+1]%mod;
cin >> n >> r;
int u, v, x, t;
FOR(i,n-1)
{
cin >> u >> v;
u--; v--;
G[u].pub(v); G[v].pub(u);
}
dfs_s(0,0,0);
dfs_hld(0,0,p++);
tag[0] = r;
X[R[0]].insert(mp(0,0));
tags.inc(st[0],r);
Free.inc(st[0],n);
ans = C(r,n+r-1);
cout << ans << '\n';
cin >> q;
FOR(i,q)
{
cin >> t;
if(t == 1)
{
cin >> v >> x;
v--;
tag[v] = x;
u = first_up(v);
int fs = S[v]-Free.get(en[v]-1)+Free.get(st[v]);
int tg = x-tags.get(en[v]-1)+tags.get(st[v]);
Free.inc(st[v],fs);
tags.inc(st[v],tg);
if(C(tg,fs+tg-1) == 0)cnt++;
else ans = (ans*C(tg,fs+tg-1))%mod;
upd(u,tg,fs);
X[R[v]].insert(mp(H[v],v));
}
else
{
cin >> v;
v--;
return 0;
}
cout << (cnt?0:ans) << '\n';
}
return 0;
}
// thank god
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
51224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
31596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
51516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
199 ms |
44240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
51224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
