UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208402#3792. Water and Ice_Alexande_1001957ms141048kbC++115.6kb2024-08-02 12:29:292024-08-02 12:57:01

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h> 
#define re register
#define il inline
#define int long long
 
using namespace std;
const int MAXN = 5e5 + 5;

il int gc() {
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)) ? EOF : *p1++;
    //return getchar();
}

il int geti() {
    re char ch = gc();
    re int f = 1, x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = gc();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = gc();
    return f * x;
}
 
int n, m;
int a[MAXN];
int to[MAXN], nxt[MAXN], head[MAXN], ecnt, ddd[MAXN];
 
il void Add(re int u, re int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
    to[++ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt;
}
 
int dep[MAXN], d;
int stt[21][MAXN], lg2[MAXN], id1[MAXN], tot, id[MAXN];
 
void DFS1(int u, int last, int depth) {
    dep[u] = depth;
    stt[0][++tot] = u;
    id1[u] = tot;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == last) continue;
        DFS1(v, u, depth + 1);
        stt[0][++tot] = u;
    }
}
 
il int Lower(re int x, re int y) {
    return dep[x] < dep[y] ? x : y;
}
 
void GetST() {
    for (re int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1;
    for (re int i = 1; (1 << i) <= tot; i++) {
        re int w = (1 << i);
        for (re int j = 1; j + w - 1 <= tot; j++) {
            stt[i][j] = Lower(stt[i - 1][j], stt[i - 1][j + w / 2]);
        }
    }
}
 
il int LCA(re int x, re int y) {
    x = id1[x]; y = id1[y];
    if (x > y) swap(x, y);
    int i = lg2[y - x + 1], w = (1 << i);
    return Lower(stt[i][x], stt[i][y - w + 1]);
} 
 
il int Dis(re int x, re int y) {
    return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}
 
int size[MAXN], maxs[MAXN];
int dfa[MAXN];
int vis[MAXN];
int dsiz[MAXN];
 
int DFS2(int u, int last, int tots) {
    size[u] = 1;
    maxs[u] = 0;
    int cen = 0;
    for (re int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v] || v == last) continue;
        int vcen = DFS2(v, u, tots);
        if (!cen || maxs[vcen] < maxs[cen]) cen = vcen;
        size[u] += size[v];
        maxs[u] = max(maxs[u], size[v]);
    }
    maxs[u] = max(maxs[u], tots - size[u]);
    if (!cen || maxs[u] < maxs[cen]) cen = u;
    return cen;
}
 
void Divide(int cen, int tots) {
    vis[cen] = 1;
    dsiz[cen] = tots;
    for (re int i = head[cen]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v]) continue;
        int vsize = (size[v] < size[cen]) ? size[v] : (tots - size[cen]);
        int vcen = DFS2(v, cen, vsize);
        dfa[vcen] = cen;
        Divide(vcen, vsize);
    }
}

struct Node{
    int sum;
    Node *ch[2];
};
 
Node npool[20000000];
int ncnt;
 
struct SegTree{
    Node *rt;
    SegTree() {rt = NULL;}
    Node *New() {return &npool[ncnt++];}
     
    void Modify(Node *&now, int pos, int k, int l, int r) {
        if (!now) now = New();
        now->sum += k;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid) Modify(now->ch[0], pos, k, l, mid);
        else Modify(now->ch[1], pos, k, mid + 1, r);
    }
     
    int Query(Node *now, int l, int r, int nl, int nr) {
        if (!now) return 0;
        if (l == nl && r == nr) return now->sum;
        int mid = (nl + nr) >> 1;
        if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
        else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
        return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
    }
};

SegTree T1[MAXN], T2[MAXN];
 
il void Modify(int idx, int val) {
    re int now = idx;
    while (now) {
        int fa = dfa[now];
        T1[now].Modify(T1[now].rt, Dis(now, idx), val, 0, dsiz[now]);
        if (fa) T2[now].Modify(T2[now].rt, Dis(fa, idx), val, 0, dsiz[fa]);
        now = fa;
    }
}
 
il int Query(int idx, int k) {
    re int res = 0;
    re int now = idx, last = 0;
    while (now) {
        int d = Dis(idx, now);
        if (d > k) {
            last = now;
            now = dfa[now];
            continue;
        }
        res += T1[now].Query(T1[now].rt, 0, k - d, 0, dsiz[now]);
        if (last) res -= T2[last].Query(T2[last].rt, 0, k - d, 0, dsiz[now]);
        last = now;
        now = dfa[now];
    }
    return res;
}
 
void Prework() {
    DFS1(1, 0, 0);
    GetST();
    int cen = DFS2(1, 0, n);
    Divide(cen, n);
}
 
signed main() {
	ios :: sync_with_stdio ( false );
	cin.tie ( 0 ), cout.tie ( 0 ); 
	cin >> n >> d;
    for (re int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        Add(x, y);
    }
    Prework();
    for ( int i = 1; i <= n; i ++ ) {
        id[i] = i;
    }
    sort ( id + 1, id + 1 + n, [] ( int x, int y ) { return dep[x] > dep[y]; } );
    int ans = 0;
    for ( int i = 1; i <= n; i ++ ) {
        int tmp = Query ( id[i], d - 1 );
        if ( !tmp ) {
            Modify ( id[i], 1 );
            ddd[id[i]] = 1;
            ans ++;
        }
    }
    /*
    for (re int i = 1; i <= m; i++) {
        int op = geti(), x = geti(), y = geti();
        x ^= ans; y ^= ans;
        if (op == 0) {
            ans = Query(x, y);
            printf("%d\n", ans);
        } else {
            Modify(x, y - a[x]);
            a[x] = y;
        }
    }
    */
    cout << ans << '\n';
    for ( int i = 1; i <= n; i ++ ) {
        if ( ddd[i] == 1 ) {
            cout << i << " ";
        }
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 9160kb

input:

10 5
3 7
7 10
7 8
9 1
5 4
3 9
7 5
3 2
7 6

output:

2
1 4 

result:

ok ok accepted

Test #2:

score: 10
Accepted
time: 5ms
memory: 9160kb

input:

10 4
8 5
8 6
1 8
4 9
5 3
7 10
8 4
7 2
1 7

output:

3
2 3 9 

result:

ok ok accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 9160kb

input:

10 3
7 8
1 10
4 3
1 5
1 7
2 9
1 4
7 2
2 6

output:

4
3 5 6 8 

result:

ok ok accepted

Test #4:

score: 10
Accepted
time: 0ms
memory: 10752kb

input:

3000 4
609 550
550 37
550 460
460 2476
2476 822
460 18
822 740
609 1212
822 2274
740 2276
2276 187
4...

output:

778
6 9 10 18 23 36 38 44 45 47 48 52 67 70 73 80 84 90 93 98 99 100 101 102 104 107 109 116 118 119...

result:

ok ok accepted

Test #5:

score: 10
Accepted
time: 3ms
memory: 10444kb

input:

3000 10
29 699
699 832
29 2332
29 1385
699 1783
832 734
1385 1639
734 2853
29 2689
2853 2190
699 558...

output:

220
22 31 61 62 98 108 115 119 137 152 169 170 178 195 221 227 229 249 263 271 278 340 345 353 360 3...

result:

ok ok accepted

Test #6:

score: 10
Accepted
time: 5ms
memory: 10180kb

input:

3000 50
444 813
444 135
813 2265
135 2309
135 914
914 535
135 2055
2055 1225
914 2499
2055 1364
2499...

output:

20
20 90 208 667 789 824 968 1275 1427 1830 1918 2137 2237 2395 2544 2553 2793 2893 2900 2973 

result:

ok ok accepted

Test #7:

score: 10
Accepted
time: 696ms
memory: 95316kb

input:

200000 217
31004 146202
108924 82624
43788 48134
199877 157947
92879 87010
198989 49945
175154 66735...

output:

924
279 304 418 471 539 566 713 1079 1355 1747 1882 1970 2494 2523 2890 3235 3626 3759 4069 4162 445...

result:

ok ok accepted

Test #8:

score: 10
Accepted
time: 766ms
memory: 90908kb

input:

200000 475
77454 87171
23492 138432
137402 34171
181862 18661
57910 51505
135417 198061
164845 19388...

output:

394
833 915 982 2281 2467 2531 2673 2886 3423 3484 5294 5459 6264 6530 7016 7839 8016 8484 9339 1085...

result:

ok ok accepted

Test #9:

score: 10
Accepted
time: 155ms
memory: 141048kb

input:

199999 4
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
1 10
10 11
1 12
12 13
1 14
14 15
1 16
16 17
1 18
18 19
1 20...

output:

99999
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67...

result:

ok ok accepted

Test #10:

score: 10
Accepted
time: 327ms
memory: 88740kb

input:

199397 946
29518 79973
29518 71183
71183 194147
29518 156561
156561 196558
196558 25260
29518 198870...

output:

159
52 101 164 243 252 621 1256 3749 5183 7067 7439 7729 7808 8065 9823 9824 9845 10945 11190 13016 ...

result:

ok ok accepted