답안 #780644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780644	2023-07-12T11:18:59 Z	Sami_Massah	Sumtree (INOI20_sumtree)	C++17	100 / 100	2207 ms	304248 KB

Main

#include <bits/stdc++.h>
using namespace std;


const int maxn = 5e5 + 12, maxk = 2e5 + 12, lg = 18, mod = 1e9 + 7;
int n, bs, tz, tms, h[maxk], col[maxk], par[maxk][lg], sz[maxk], st[maxk], en[maxk],  sum1[maxk * 3], sum2[maxk * 3];
long long ans, fact[maxn], rfact[maxn];
set <pair<int, int>> Q[maxk * 3];
vector <int> conn[maxk];
bitset <maxn> marked, zero;
long long tav(long long a, long long b){
    if(b == 0)
        return 1;
    a %= mod;
    long long x = tav(a * a % mod, b / 2);
    if(b % 2)
        return x * a % mod;
    return x % mod;
}

void update_tree1(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        sum1[u] = k;
        return;
    }
    int mid = (L + R) / 2;
    update_tree1(l, r, u * 2, k, L, mid);
    update_tree1(l, r, u * 2 + 1, k, mid + 1, R);
    sum1[u] = sum1[u * 2] + sum1[u * 2 + 1];
}
void update_tree2(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        sum2[u] = k;
        return;
    }
    int mid = (L + R) / 2;
    update_tree2(l, r, u * 2, k, L, mid);
    update_tree2(l, r, u * 2 + 1, k, mid + 1, R);
    sum2[u] = sum2[u * 2] + sum2[u * 2 + 1];
}
int get_sum1(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return 0;
    if(l <= L && R <= r)
        return sum1[u];
    int mid = (L + R) / 2;
    return get_sum1(l, r, u * 2, L, mid) + get_sum1(l, r, u * 2 + 1, mid + 1, R);
}
int get_sum2(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return 0;
    if(l <= L && R <= r)
        return sum2[u];
    int mid = (L + R) / 2;
    return get_sum2(l, r, u * 2, L, mid) + get_sum2(l, r, u * 2 + 1, mid + 1, R);
}
void dfs_set(int u){
    marked[u] = 1;
    sz[u] = 1;
    st[u] = tms;
    tms += 1;
    for(int i = 0; i + 1 < lg; i++)
        par[u][i + 1] = par[par[u][i]][i];
    for(int v: conn[u])
        if(!marked[v]){
            par[v][0] = u;
            h[v] = h[u] + 1;
            dfs_set(v);
            sz[u] += sz[v];

        }
    en[u] = tms - 1;
}
void add_to_tree(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        Q[u].insert(make_pair(h[k], k));
        return;
    }
    int mid = (L + R) / 2;
    add_to_tree(l, r, u * 2, k, L, mid);
    add_to_tree(l, r, u * 2 + 1, k, mid + 1, R);
}
void erase_from_tree(int l, int r, int u, int k, int L = 0, int R = n){
    if(r < L || R < l)
        return;
    if(l <= L && R <= r){
        Q[u].erase(make_pair(h[k], k));
        return;
    }
    int mid = (L + R) / 2;
    erase_from_tree(l, r, u * 2, k, L, mid);
    erase_from_tree(l, r, u * 2 + 1, k, mid + 1, R);
}
pair<int, int> find_pd(int l, int r, int u, int L = 0, int R = n){
    if(r < L || R < l)
        return make_pair(-1, 0);
    if(l <= L && R <= r){
        if(Q[u].size() == 0)
            return make_pair(-1, 0);
        return *Q[u].rbegin();
    }
    auto x = make_pair(-1, 0);
    if(Q[u].size())
        x = *Q[u].rbegin();
    int mid = (L + R) / 2;
    return max({find_pd(l, r, u * 2, L, mid), find_pd(l, r, u * 2 + 1, mid + 1, R), x});
}
long long get_c(int a, int b){
    if(a < b)
        return 0;
    return fact[a] * (rfact[b] * rfact[a - b] % mod) % mod;

}
void add_tree(int u, int k){
    int pd = find_pd(st[u], st[u], 1).second;
 //   cout << u << ' ' << pd << endl;
   // cout << u << ' ' << pd << endl;
    col[u] = k;
    if(u != 1){
        int x = get_sum1(st[pd] + 1, en[pd], 1);
        int d = get_sum2(st[pd] + 1, en[pd], 1);

        if(zero[pd] == 0){
            x = sz[pd] - x;
            d = col[pd] - d;
            long long f = get_c(d + x - 1, x - 1);
            ans = ans * tav(f, mod - 2) % mod;
        }
    }
  //  cout << ans << endl;
    int x = get_sum1(st[u], en[u], 1);
    int d = get_sum2(st[u], en[u], 1);
    update_tree1(st[u], st[u], 1, sz[u] - x);
    update_tree2(st[u], st[u], 1, k - d);
    add_to_tree(st[u] + 1, en[u], 1, u);
   // cout << st[pd] << '-' << en[pd] << endl;
    if(k < d){
        zero[u] = 1;
        tz += 1;
    }
    else{
 //       cout << x << ' ' << sz[u] << endl;
        x = sz[u] - x;
        d = k - d;
      //  cout << x << ' ' << d << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * f % mod;
    }
   // cout << ans << endl;

    if(u != 1){
        int x = get_sum1(st[pd] + 1, en[pd], 1);
        int d = get_sum2(st[pd] + 1, en[pd], 1);
        update_tree1(st[pd], st[pd], 1, sz[pd] - x);
        update_tree2(st[pd], st[pd], 1, col[pd] - d);
        if(col[pd] < d){
            tz += (1 - zero[pd]);
            zero[pd] = 1;
        }
        else{
            x = sz[pd] - x;
            d = col[pd] - d;
            tz -= zero[pd];
            zero[pd] = 0;
    //        cout << x << ' ' << d << endl;
            long long f = get_c(d + x - 1, x - 1);
            ans = ans * f % mod;
        }
    }
    //cout << ans << endl << endl;
}
void remove_tree(int u){

    int pd = find_pd(st[u], st[u], 1).second;
   // cout << u << ' ' << pd << endl;
    int x = get_sum1(st[pd] + 1, en[pd], 1);
    int d = get_sum2(st[pd] + 1, en[pd], 1);

    if(zero[pd] == 0){
        x = sz[pd] - x;
        d = col[pd] - d;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * tav(f, mod - 2) % mod;
    }

    x = get_sum1(st[u] + 1, en[u], 1);
    d = get_sum2(st[u] + 1, en[u], 1);

    update_tree1(st[u], st[u], 1, 0);
    update_tree2(st[u], st[u], 1, 0);
    erase_from_tree(st[u] + 1, en[u], 1, u);
    //cout << get_sum1(1, n, 1) << endl;
    if(col[u] < d){
        tz -= zero[u];
        zero[u] = 0;
    }
    else{
        tz -= zero[u];
        zero[u] = 0;
        x = sz[u] - x;
        d = col[u] - d;
    //    cout << d << ' ' << x << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * tav(f, mod - 2) % mod;
    }
    col[u] = -1;


    x = get_sum1(st[pd] + 1, en[pd], 1);
    d = get_sum2(st[pd] + 1, en[pd], 1);

    update_tree1(st[pd], st[pd], 1, sz[pd] - x);
    update_tree2(st[pd], st[pd], 1, col[pd] - d);

    if(col[pd] < d){
        tz += (1 - zero[pd]);
        zero[pd] = 1;
    }
    else{
        tz -= (zero[pd]);
        zero[pd] = 0;
        x = sz[pd] - x;
        d = col[pd] - d;
      //  cout << d << ' ' << x << endl;
        long long f = get_c(d + x - 1, x - 1);
        ans = ans * f % mod;
    }
}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    memset(col, -1, sizeof col);
    col[0] = 0;
    fact[0] = 1;
    for(int i = 1; i < maxn; i++)
        fact[i] = fact[i - 1] * i % mod;
    for(int i = 0; i < maxn; i++)
        rfact[i] = tav(fact[i], mod - 2) % mod;
    cin >> n >> bs;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    cout << endl;
    dfs_set(1);

    ans = 1;
    add_tree(1, bs);
    cout << ans << "\n";
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int a;
        int b, c;
        cin >> a;
        if(a == 1){
            cin >> b >> c;
            add_tree(b, c);
        }
        else{
            cin >> b;
            remove_tree(b);
        }
        if(tz)
            cout << 0 << "\n";
        else
            cout << ans << "\n";

    }





}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	73624 KB	Output is correct
2	Correct	237 ms	73616 KB	Output is correct
3	Correct	236 ms	73676 KB	Output is correct
4	Correct	248 ms	73584 KB	Output is correct
5	Correct	212 ms	69632 KB	Output is correct
6	Correct	121 ms	42480 KB	Output is correct
7	Correct	125 ms	42160 KB	Output is correct
8	Correct	121 ms	42224 KB	Output is correct
9	Correct	239 ms	66016 KB	Output is correct
10	Correct	262 ms	65840 KB	Output is correct
11	Correct	266 ms	66100 KB	Output is correct
12	Correct	239 ms	64844 KB	Output is correct
13	Correct	218 ms	71292 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	41712 KB	Output is correct
2	Correct	121 ms	41788 KB	Output is correct
3	Correct	121 ms	41816 KB	Output is correct
4	Correct	121 ms	41804 KB	Output is correct
5	Correct	122 ms	41824 KB	Output is correct
6	Correct	125 ms	42136 KB	Output is correct
7	Correct	126 ms	42108 KB	Output is correct
8	Correct	125 ms	42136 KB	Output is correct
9	Correct	128 ms	42360 KB	Output is correct
10	Correct	130 ms	42444 KB	Output is correct
11	Correct	129 ms	42536 KB	Output is correct
12	Correct	122 ms	42372 KB	Output is correct
13	Correct	135 ms	42464 KB	Output is correct
14	Correct	135 ms	42420 KB	Output is correct
15	Correct	133 ms	42844 KB	Output is correct
16	Correct	128 ms	42300 KB	Output is correct
17	Correct	129 ms	42444 KB	Output is correct
18	Correct	132 ms	42272 KB	Output is correct
19	Correct	126 ms	42284 KB	Output is correct
20	Correct	125 ms	42148 KB	Output is correct
21	Correct	125 ms	42072 KB	Output is correct
22	Correct	122 ms	41820 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	273 ms	79512 KB	Output is correct
2	Correct	377 ms	84824 KB	Output is correct
3	Correct	274 ms	80564 KB	Output is correct
4	Correct	477 ms	93924 KB	Output is correct
5	Correct	1147 ms	146028 KB	Output is correct
6	Correct	126 ms	43080 KB	Output is correct
7	Correct	123 ms	42272 KB	Output is correct
8	Correct	126 ms	42624 KB	Output is correct
9	Correct	590 ms	76724 KB	Output is correct
10	Correct	564 ms	75076 KB	Output is correct
11	Correct	509 ms	74684 KB	Output is correct
12	Correct	603 ms	75060 KB	Output is correct
13	Correct	2207 ms	303720 KB	Output is correct
14	Correct	2078 ms	304240 KB	Output is correct
15	Correct	2116 ms	304248 KB	Output is correct
16	Correct	2077 ms	304128 KB	Output is correct
17	Correct	2075 ms	304204 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	852 ms	72364 KB	Output is correct
2	Correct	815 ms	72180 KB	Output is correct
3	Correct	845 ms	72456 KB	Output is correct
4	Correct	851 ms	72436 KB	Output is correct
5	Correct	846 ms	71060 KB	Output is correct
6	Correct	840 ms	72296 KB	Output is correct
7	Correct	695 ms	58332 KB	Output is correct
8	Correct	742 ms	58468 KB	Output is correct
9	Correct	816 ms	72288 KB	Output is correct
10	Correct	821 ms	72412 KB	Output is correct
11	Correct	860 ms	72276 KB	Output is correct
12	Correct	708 ms	58352 KB	Output is correct
13	Correct	526 ms	55308 KB	Output is correct
14	Correct	607 ms	56780 KB	Output is correct
15	Correct	627 ms	56788 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	73624 KB	Output is correct
2	Correct	237 ms	73616 KB	Output is correct
3	Correct	236 ms	73676 KB	Output is correct
4	Correct	248 ms	73584 KB	Output is correct
5	Correct	212 ms	69632 KB	Output is correct
6	Correct	121 ms	42480 KB	Output is correct
7	Correct	125 ms	42160 KB	Output is correct
8	Correct	121 ms	42224 KB	Output is correct
9	Correct	239 ms	66016 KB	Output is correct
10	Correct	262 ms	65840 KB	Output is correct
11	Correct	266 ms	66100 KB	Output is correct
12	Correct	239 ms	64844 KB	Output is correct
13	Correct	218 ms	71292 KB	Output is correct
14	Correct	123 ms	41712 KB	Output is correct
15	Correct	121 ms	41788 KB	Output is correct
16	Correct	121 ms	41816 KB	Output is correct
17	Correct	121 ms	41804 KB	Output is correct
18	Correct	122 ms	41824 KB	Output is correct
19	Correct	125 ms	42136 KB	Output is correct
20	Correct	126 ms	42108 KB	Output is correct
21	Correct	125 ms	42136 KB	Output is correct
22	Correct	128 ms	42360 KB	Output is correct
23	Correct	130 ms	42444 KB	Output is correct
24	Correct	129 ms	42536 KB	Output is correct
25	Correct	122 ms	42372 KB	Output is correct
26	Correct	135 ms	42464 KB	Output is correct
27	Correct	135 ms	42420 KB	Output is correct
28	Correct	133 ms	42844 KB	Output is correct
29	Correct	128 ms	42300 KB	Output is correct
30	Correct	129 ms	42444 KB	Output is correct
31	Correct	132 ms	42272 KB	Output is correct
32	Correct	126 ms	42284 KB	Output is correct
33	Correct	125 ms	42148 KB	Output is correct
34	Correct	125 ms	42072 KB	Output is correct
35	Correct	122 ms	41820 KB	Output is correct
36	Correct	273 ms	79512 KB	Output is correct
37	Correct	377 ms	84824 KB	Output is correct
38	Correct	274 ms	80564 KB	Output is correct
39	Correct	477 ms	93924 KB	Output is correct
40	Correct	1147 ms	146028 KB	Output is correct
41	Correct	126 ms	43080 KB	Output is correct
42	Correct	123 ms	42272 KB	Output is correct
43	Correct	126 ms	42624 KB	Output is correct
44	Correct	590 ms	76724 KB	Output is correct
45	Correct	564 ms	75076 KB	Output is correct
46	Correct	509 ms	74684 KB	Output is correct
47	Correct	603 ms	75060 KB	Output is correct
48	Correct	2207 ms	303720 KB	Output is correct
49	Correct	2078 ms	304240 KB	Output is correct
50	Correct	2116 ms	304248 KB	Output is correct
51	Correct	2077 ms	304128 KB	Output is correct
52	Correct	2075 ms	304204 KB	Output is correct
53	Correct	852 ms	72364 KB	Output is correct
54	Correct	815 ms	72180 KB	Output is correct
55	Correct	845 ms	72456 KB	Output is correct
56	Correct	851 ms	72436 KB	Output is correct
57	Correct	846 ms	71060 KB	Output is correct
58	Correct	840 ms	72296 KB	Output is correct
59	Correct	695 ms	58332 KB	Output is correct
60	Correct	742 ms	58468 KB	Output is correct
61	Correct	816 ms	72288 KB	Output is correct
62	Correct	821 ms	72412 KB	Output is correct
63	Correct	860 ms	72276 KB	Output is correct
64	Correct	708 ms	58352 KB	Output is correct
65	Correct	526 ms	55308 KB	Output is correct
66	Correct	607 ms	56780 KB	Output is correct
67	Correct	627 ms	56788 KB	Output is correct
68	Correct	129 ms	41736 KB	Output is correct
69	Correct	121 ms	41732 KB	Output is correct
70	Correct	993 ms	80156 KB	Output is correct
71	Correct	943 ms	80052 KB	Output is correct
72	Correct	954 ms	79992 KB	Output is correct
73	Correct	982 ms	80200 KB	Output is correct
74	Correct	1111 ms	80640 KB	Output is correct
75	Correct	1043 ms	76100 KB	Output is correct
76	Correct	831 ms	72308 KB	Output is correct
77	Correct	861 ms	72948 KB	Output is correct
78	Correct	941 ms	74024 KB	Output is correct
79	Correct	963 ms	76180 KB	Output is correct
80	Correct	1066 ms	75476 KB	Output is correct
81	Correct	1034 ms	76392 KB	Output is correct
82	Correct	690 ms	68672 KB	Output is correct
83	Correct	676 ms	75868 KB	Output is correct
84	Correct	731 ms	75064 KB	Output is correct
85	Correct	694 ms	75068 KB	Output is correct