对于点分治的小疑问

P3806 【模板】点分治 1

lottle1212 @ 2023-07-24 21:15:30

像我这种写法的,\operatorname{get\ rt} 函数当传入的 u 不等于最终的 rt 时,则 sz 数组是以 u 为根而非以 rt 为根,那么在 \operatorname{divide} 函数中再次 \operatorname{get \ rt} 前,若枚举到的 v 恰为 u 的父亲,则 sum 的初始值就不是当前子树的大小了。可这样仍然可以 AC,这是为什么?

#include <iostream>
using namespace std;
typedef long long ll;
const ll N = 1e4 + 10, M = 1e2 + 10, INF = 1e7 + 10;
ll n, m, u, v, w, cnt, tot, Min, sum, rt, head[N], sz[N], dis[N], d[N], q[INF], ask[M];
bool del[N], ans[M], judge[INF];
ll rd() {
    ll sum = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
    return f ? -sum : sum;
}
struct Edge { ll nxt, to, w; } e[N << 1];
void add(ll u, ll v, ll w) { e[++ cnt] = {head[u], v, w}; head[u] = cnt; }
void get_rt(ll u, ll pre) {
    sz[u] = 1; ll mx = 0;
    for (ll i = head[u], v; i; i = e[i].nxt) {
        v = e[i].to;
        if (v == pre || del[v]) continue;
        get_rt(v, u);
        sz[u] += sz[v], mx = max(mx, sz[v]);
    }
    mx = max(mx, sum - sz[u]);
    if (mx < Min) Min = mx, rt = u;
}
void get_dis(ll u, ll pre) {
    dis[++ tot] = d[u];
    for (ll i = head[u], v; i; i = e[i].nxt) {
        v = e[i].to;
        if (v == pre || del[v]) continue;
        d[v] = d[u] + e[i].w;
        get_dis(v, u);
    }
}
void calc(ll u) {
    del[u] = judge[0] = 1; ll top = 0;
    for (ll i = head[u], v; i; i = e[i].nxt) {
        v = e[i].to;
        if (del[v]) continue;
        tot = 0, d[v] = e[i].w;
        get_dis(v, u);
        for (ll j = 1; j <= tot; ++ j)
            for (ll k = 1; k <= m; ++ k)
                if (ask[k] >= dis[j])
                    ans[k] |= judge[ask[k] - dis[j]];
        for (ll j = 1; j <= tot; ++ j)
            if (dis[j] < INF)
                q[++ top] = dis[j], judge[dis[j]] = 1;
    }
    for (ll i = 1; i <= top; ++ i) judge[q[i]] = 0;
}
void divide(ll u) {
    calc(u);
    for (ll i = head[u], v; i; i = e[i].nxt) {
        v = e[i].to;
        if (del[v]) continue;
        Min = sum = sz[v];
        get_rt(v, 0);
        divide(rt);
    }
}
signed main() {
    n = rd(), m = rd();
    for (ll i = 1; i < n; ++ i) u = rd(), v = rd(), w = rd(), add(u, v, w), add(v, u, w);
    for (ll i = 1; i <= m; ++ i) ask[i] = rd();
    Min = sum = n, get_rt(1, 0);
    divide(rt);
    for (ll i = 1; i <= m; ++ i) puts(ans[i] ? "AYE" : "NAY");
    return 0;
}

by zzafanti @ 2023-07-26 07:17:25

lca的这篇博客 说了这个问题,这么做不影响复杂度,您可以看一下qwq


|