Luogu P4178 Tree

不建议使用 Luogu 3806 作为模板，该题情形过于特殊，只需找到一组解即可判断为 true，导致只遍历树的一部分也可通过此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool vis[MAXn + 10];
int cen, siz[MAXn + 10];
void EvaCen(int cur, int f, int totsiz) {/* ... */}

int cntd, d[MAXn + 10];
void Dfs(int cur, int f, int dis, int tar) {
    if (dis > tar) return;
    d[++cntd] = dis;
    for (int i = head[cur]; i; i = nex[i]) {
        if (to[i] == f || vis[to[i]]) continue;
        Dfs(to[i], cur, dis + wei[i], tar);
    }
}

int ans;
int top, stk[MAXn + 10];
void Div(int bg, int totsiz, int tar) {
    EvaCen(bg, 0, totsiz);
    int c = cen;
    vis[c] = 1;
    while (top) Add(stk[top--], -1, tar);
    for (int i = head[c]; i; i = nex[i]) {
        if (vis[to[i]]) continue;
        cntd = 0;
        Dfs(to[i], c, wei[i], tar);
        for (int i = 1; i <= cntd; ++i) {
            ans += Sum(tar - d[i]);
        }
        for (int i = 1; i <= cntd; ++i) {
            Add(d[i], 1, tar);
            stk[++top] = d[i];
        }
    }
    for (int i = head[c]; i; i = nex[i]) {
        if (vis[to[i]]) continue;
        if (siz[to[i]] < siz[c]) Div(to[i], siz[to[i]], tar);
        else Div(to[i], totsiz - siz[c], tar);
    }
}

signed main() {
    // ...
    Add(0, 1, tar);
    Div(1, n, tar);
}