# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
999374 |
2024-06-15T11:41:39 Z |
fuad27 |
Sumtree (INOI20_sumtree) |
C++17 |
|
680 ms |
88144 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], tagsms[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;
}
};
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]);
}
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++;
}
struct DS1 {
int fen[3*N];
DS1() {
for(int i = 0;i<3*N;i++)fen[i]=0;
}
void upd(int at, int val) {
at++;
while(at<3*N) {
fen[at]+=val;
at+=at&(-at);
}
}
void update(int l, int r, int val) {
upd(l, val);
upd(r+1, -val);
}
long long get(int at) {
at++;
long long res=0;
while(at) {
res+=fen[at];
at-=at&(-at);
}
return res;
}
};
namespace HLD1 {
DS1 ds;
int tin[N], top[N], tim=0, par[N], V[N];
void dfs(int at, int p, int tp) {
tin[at]=++tim;
top[at]=tp;
par[at]=p;
int big=-1;
for(int to:g[at]) {
if(to==p)continue;
if(big==-1 or sz[to]>sz[big]) {
big=to;
}
}
if(big==-1)return;
dfs(big, at, tp);
for(int to:g[at]) {
if(to==big or to==p)continue;
dfs(to, at, to);
}
}
int upd(int u,int v, long long val) {
int ans=0;
while(top[u]!=top[v]) {
if(depth[top[u]] < depth[top[v]])swap(u,v);
ds.update(tin[top[u]], tin[u], val);
u=par[top[u]];
}
if(depth[u]>depth[v])swap(u,v);
ds.update(tin[u], tin[v], val);
return ans;
}
long long get(int u) {
return ds.get(tin[u]);
}
};
namespace HLD2 {
DS1 ds;
int tin[N], top[N], tim=0, par[N], V[N];
void dfs(int at, int p, int tp) {
tin[at]=++tim;
top[at]=tp;
par[at]=p;
int big=-1;
for(int to:g[at]) {
if(to==p)continue;
if(big==-1 or sz[to]>sz[big]) {
big=to;
}
}
if(big==-1)return;
dfs(big, at, tp);
for(int to:g[at]) {
if(to==big or to==p)continue;
dfs(to, at, to);
}
}
int upd(int u,int v, int val) {
int ans=0;
while(top[u]!=top[v]) {
if(depth[top[u]] < depth[top[v]])swap(u,v);
ds.update(tin[top[u]], tin[u], val);
u=par[top[u]];
}
if(depth[u]>depth[v])swap(u,v);
ds.update(tin[u], tin[v], val);
return ans;
}
int get(int u) {
return ds.get(tin[u]);
}
};
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);
HLD1::dfs(1, 0, 1);
HLD2::dfs(1, 0, 1);
tags[1] = r;
used[1] = 1;
for(int i = 2;i<=n;i++){
change(i, 1);
}
for(int i= 1;i<=n;i++) {
HLD1::upd(i, i, sz[i]);
HLD2::upd(i, i, tagsms[i]);
}
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;
int rr = findroot(u);
{
long long tmp = tags[rr] - HLD2::get(rr);
long long szz = HLD1::get(rr);
ans.del(ncr(szz+tmp-1, tmp));
}
int par = up[u][0];
HLD1::upd(par, rr, -HLD1::get(u));
HLD2::upd(par, rr, v-HLD2::get(u));
// while(1) {
// sz[par]-=sz[u];
// tagsms[par]-=tagsms[u];
// tagsms[par]+=v;
// if(par==rr)break;
// par = up[par][0];
// }
{
long long tmp = tags[u] - HLD2::get(u);
long long szz = HLD1::get(u);
ans.add(ncr(szz+tmp-1, tmp));
}
{
long long tmp = tags[rr] - HLD2::get(rr);
long long szz = HLD1::get(rr);
ans.add(ncr(szz+tmp-1, tmp));
}
change(u, -1);
}
else {
int u;
cin >> u;
int v = tags[u];
change(u, 1);
int rr = findroot(u);
{
long long tmp = tags[rr] - HLD2::get(rr);
long long szz = HLD1::get(rr);
ans.del(ncr(szz+tmp-1, tmp));
}
int par = up[u][0];
HLD1::upd(par, rr, HLD1::get(u));
HLD2::upd(par, rr, HLD2::get(u)-v);
// while(1) {
// sz[par]+=sz[u];
// tagsms[par]+=tagsms[u];
// tagsms[par]-=v;
// if(par==rr)break;
// par = up[par][0];
// }
{
long long tmp = tags[u] - HLD2::get(u);
long long szz = HLD1::get(u);
ans.del(ncr(szz+tmp-1, tmp));
}
{
long long tmp = tags[rr] - HLD2::get(rr);
long long szz = HLD1::get(rr);
ans.add(ncr(szz+tmp-1, tmp));
}
}
cout << ans.get() << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
76628 KB |
Output is correct |
2 |
Correct |
131 ms |
76628 KB |
Output is correct |
3 |
Correct |
155 ms |
76588 KB |
Output is correct |
4 |
Correct |
130 ms |
76624 KB |
Output is correct |
5 |
Correct |
108 ms |
72448 KB |
Output is correct |
6 |
Correct |
9 ms |
42844 KB |
Output is correct |
7 |
Correct |
9 ms |
42592 KB |
Output is correct |
8 |
Correct |
9 ms |
42584 KB |
Output is correct |
9 |
Correct |
134 ms |
69004 KB |
Output is correct |
10 |
Correct |
128 ms |
68948 KB |
Output is correct |
11 |
Correct |
132 ms |
68944 KB |
Output is correct |
12 |
Correct |
117 ms |
67996 KB |
Output is correct |
13 |
Correct |
113 ms |
73040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
42332 KB |
Output is correct |
2 |
Correct |
7 ms |
42388 KB |
Output is correct |
3 |
Correct |
8 ms |
42332 KB |
Output is correct |
4 |
Correct |
8 ms |
42384 KB |
Output is correct |
5 |
Correct |
10 ms |
42328 KB |
Output is correct |
6 |
Correct |
13 ms |
42584 KB |
Output is correct |
7 |
Correct |
12 ms |
42584 KB |
Output is correct |
8 |
Correct |
12 ms |
42588 KB |
Output is correct |
9 |
Correct |
15 ms |
42584 KB |
Output is correct |
10 |
Correct |
14 ms |
42756 KB |
Output is correct |
11 |
Correct |
14 ms |
42840 KB |
Output is correct |
12 |
Correct |
9 ms |
42588 KB |
Output is correct |
13 |
Correct |
14 ms |
42644 KB |
Output is correct |
14 |
Correct |
14 ms |
42692 KB |
Output is correct |
15 |
Correct |
16 ms |
42844 KB |
Output is correct |
16 |
Correct |
17 ms |
42588 KB |
Output is correct |
17 |
Correct |
14 ms |
42588 KB |
Output is correct |
18 |
Correct |
13 ms |
42640 KB |
Output is correct |
19 |
Correct |
15 ms |
42672 KB |
Output is correct |
20 |
Correct |
11 ms |
42400 KB |
Output is correct |
21 |
Correct |
11 ms |
42588 KB |
Output is correct |
22 |
Correct |
8 ms |
42332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
75944 KB |
Output is correct |
2 |
Correct |
198 ms |
76116 KB |
Output is correct |
3 |
Correct |
153 ms |
76628 KB |
Output is correct |
4 |
Correct |
233 ms |
77208 KB |
Output is correct |
5 |
Correct |
328 ms |
74248 KB |
Output is correct |
6 |
Correct |
11 ms |
42840 KB |
Output is correct |
7 |
Correct |
11 ms |
42588 KB |
Output is correct |
8 |
Correct |
12 ms |
42680 KB |
Output is correct |
9 |
Correct |
382 ms |
70376 KB |
Output is correct |
10 |
Correct |
297 ms |
69964 KB |
Output is correct |
11 |
Correct |
272 ms |
69716 KB |
Output is correct |
12 |
Correct |
250 ms |
69652 KB |
Output is correct |
13 |
Correct |
425 ms |
88092 KB |
Output is correct |
14 |
Correct |
435 ms |
87892 KB |
Output is correct |
15 |
Correct |
450 ms |
87884 KB |
Output is correct |
16 |
Correct |
449 ms |
88144 KB |
Output is correct |
17 |
Correct |
422 ms |
87884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
592 ms |
71876 KB |
Output is correct |
2 |
Correct |
573 ms |
71856 KB |
Output is correct |
3 |
Correct |
581 ms |
71872 KB |
Output is correct |
4 |
Correct |
573 ms |
71872 KB |
Output is correct |
5 |
Correct |
565 ms |
70992 KB |
Output is correct |
6 |
Correct |
588 ms |
71508 KB |
Output is correct |
7 |
Correct |
489 ms |
57496 KB |
Output is correct |
8 |
Correct |
479 ms |
57684 KB |
Output is correct |
9 |
Correct |
575 ms |
72020 KB |
Output is correct |
10 |
Correct |
583 ms |
72012 KB |
Output is correct |
11 |
Correct |
632 ms |
72016 KB |
Output is correct |
12 |
Correct |
494 ms |
57528 KB |
Output is correct |
13 |
Correct |
331 ms |
56144 KB |
Output is correct |
14 |
Correct |
335 ms |
55956 KB |
Output is correct |
15 |
Correct |
380 ms |
56148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
76628 KB |
Output is correct |
2 |
Correct |
131 ms |
76628 KB |
Output is correct |
3 |
Correct |
155 ms |
76588 KB |
Output is correct |
4 |
Correct |
130 ms |
76624 KB |
Output is correct |
5 |
Correct |
108 ms |
72448 KB |
Output is correct |
6 |
Correct |
9 ms |
42844 KB |
Output is correct |
7 |
Correct |
9 ms |
42592 KB |
Output is correct |
8 |
Correct |
9 ms |
42584 KB |
Output is correct |
9 |
Correct |
134 ms |
69004 KB |
Output is correct |
10 |
Correct |
128 ms |
68948 KB |
Output is correct |
11 |
Correct |
132 ms |
68944 KB |
Output is correct |
12 |
Correct |
117 ms |
67996 KB |
Output is correct |
13 |
Correct |
113 ms |
73040 KB |
Output is correct |
14 |
Correct |
7 ms |
42332 KB |
Output is correct |
15 |
Correct |
7 ms |
42388 KB |
Output is correct |
16 |
Correct |
8 ms |
42332 KB |
Output is correct |
17 |
Correct |
8 ms |
42384 KB |
Output is correct |
18 |
Correct |
10 ms |
42328 KB |
Output is correct |
19 |
Correct |
13 ms |
42584 KB |
Output is correct |
20 |
Correct |
12 ms |
42584 KB |
Output is correct |
21 |
Correct |
12 ms |
42588 KB |
Output is correct |
22 |
Correct |
15 ms |
42584 KB |
Output is correct |
23 |
Correct |
14 ms |
42756 KB |
Output is correct |
24 |
Correct |
14 ms |
42840 KB |
Output is correct |
25 |
Correct |
9 ms |
42588 KB |
Output is correct |
26 |
Correct |
14 ms |
42644 KB |
Output is correct |
27 |
Correct |
14 ms |
42692 KB |
Output is correct |
28 |
Correct |
16 ms |
42844 KB |
Output is correct |
29 |
Correct |
17 ms |
42588 KB |
Output is correct |
30 |
Correct |
14 ms |
42588 KB |
Output is correct |
31 |
Correct |
13 ms |
42640 KB |
Output is correct |
32 |
Correct |
15 ms |
42672 KB |
Output is correct |
33 |
Correct |
11 ms |
42400 KB |
Output is correct |
34 |
Correct |
11 ms |
42588 KB |
Output is correct |
35 |
Correct |
8 ms |
42332 KB |
Output is correct |
36 |
Correct |
173 ms |
75944 KB |
Output is correct |
37 |
Correct |
198 ms |
76116 KB |
Output is correct |
38 |
Correct |
153 ms |
76628 KB |
Output is correct |
39 |
Correct |
233 ms |
77208 KB |
Output is correct |
40 |
Correct |
328 ms |
74248 KB |
Output is correct |
41 |
Correct |
11 ms |
42840 KB |
Output is correct |
42 |
Correct |
11 ms |
42588 KB |
Output is correct |
43 |
Correct |
12 ms |
42680 KB |
Output is correct |
44 |
Correct |
382 ms |
70376 KB |
Output is correct |
45 |
Correct |
297 ms |
69964 KB |
Output is correct |
46 |
Correct |
272 ms |
69716 KB |
Output is correct |
47 |
Correct |
250 ms |
69652 KB |
Output is correct |
48 |
Correct |
425 ms |
88092 KB |
Output is correct |
49 |
Correct |
435 ms |
87892 KB |
Output is correct |
50 |
Correct |
450 ms |
87884 KB |
Output is correct |
51 |
Correct |
449 ms |
88144 KB |
Output is correct |
52 |
Correct |
422 ms |
87884 KB |
Output is correct |
53 |
Correct |
592 ms |
71876 KB |
Output is correct |
54 |
Correct |
573 ms |
71856 KB |
Output is correct |
55 |
Correct |
581 ms |
71872 KB |
Output is correct |
56 |
Correct |
573 ms |
71872 KB |
Output is correct |
57 |
Correct |
565 ms |
70992 KB |
Output is correct |
58 |
Correct |
588 ms |
71508 KB |
Output is correct |
59 |
Correct |
489 ms |
57496 KB |
Output is correct |
60 |
Correct |
479 ms |
57684 KB |
Output is correct |
61 |
Correct |
575 ms |
72020 KB |
Output is correct |
62 |
Correct |
583 ms |
72012 KB |
Output is correct |
63 |
Correct |
632 ms |
72016 KB |
Output is correct |
64 |
Correct |
494 ms |
57528 KB |
Output is correct |
65 |
Correct |
331 ms |
56144 KB |
Output is correct |
66 |
Correct |
335 ms |
55956 KB |
Output is correct |
67 |
Correct |
380 ms |
56148 KB |
Output is correct |
68 |
Correct |
8 ms |
42332 KB |
Output is correct |
69 |
Correct |
7 ms |
42332 KB |
Output is correct |
70 |
Correct |
609 ms |
79508 KB |
Output is correct |
71 |
Correct |
617 ms |
79700 KB |
Output is correct |
72 |
Correct |
621 ms |
79444 KB |
Output is correct |
73 |
Correct |
610 ms |
79444 KB |
Output is correct |
74 |
Correct |
627 ms |
79488 KB |
Output is correct |
75 |
Correct |
630 ms |
75528 KB |
Output is correct |
76 |
Correct |
617 ms |
71912 KB |
Output is correct |
77 |
Correct |
573 ms |
71508 KB |
Output is correct |
78 |
Correct |
514 ms |
70740 KB |
Output is correct |
79 |
Correct |
664 ms |
75736 KB |
Output is correct |
80 |
Correct |
671 ms |
74924 KB |
Output is correct |
81 |
Correct |
680 ms |
75600 KB |
Output is correct |
82 |
Correct |
453 ms |
70288 KB |
Output is correct |
83 |
Correct |
539 ms |
79104 KB |
Output is correct |
84 |
Correct |
434 ms |
78184 KB |
Output is correct |
85 |
Correct |
421 ms |
78160 KB |
Output is correct |