关于点分治的一个疑问

SakurajiamaMai @ 2024-07-11 20:55:35

by SakurajiamaMai @ 2024-07-11 20:56:26

这是不去重的

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10, mod = 1e9 + 7;
struct node{
    int u, w;
};
vector<node> g[N];
int sz[N], dp[N], dist[N], wait[N];
int now, Tsize, cnt, k, res, n, m;
bool vis[N], ok[N];
void dfs1(int u, int fa){
    sz[u] = 1, dp[u] = 0;
    for(auto it : g[u]){
        int x = it.u;
        if(x == fa || vis[x]) continue;
        dfs1(x, u);
        sz[u] += sz[x];
        dp[u] = max(dp[u], sz[x]); 
    }
    dp[u] = max(dp[u], Tsize - sz[u]);
    if(dp[u] < dp[now]) now = u;
}
void dfs2(int u, int fa, int d){
    dist[++cnt] = d;
    for(auto it : g[u]){
        int x = it.u, w = it.w;
        if(x == fa || vis[x]) continue;
        dfs2(x, u, d + w);
    }
}
void dfs3(int u, int d){
    cnt = 0, dfs2(u, 0, d);
    sort(dist + 1, dist + 1 + cnt);
    for(int j = 1; j <= m; j++){
        if(ok[j]) continue;
        for(int i = 1; i < cnt; i++){
            int x = lower_bound(dist + i + 1, dist + 1 + cnt, wait[j] - dist[i]) - dist;
            if(x && x <= cnt && dist[x] + dist[i] == wait[j] && x != i) ok[j] = true;
        }
    }
}
void dfs(int u){
    dfs3(u, 0), vis[u] = true;
    for(auto it : g[u]){
        int x = it.u, w = it.w;
        if(vis[x]) continue;
        now = 0, Tsize = sz[x], dfs1(x, 0);
        dfs(now);
    }
}
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c}), g[b].push_back({a, c});
    }
    for(int i =1; i <= m; i++) cin >> wait[i];
    dp[now = 0] = 1e9, Tsize = n, dfs1(1, 0);
    dfs(now);
    for(int i = 1; i <= m; i++){
        if(ok[i]) cout << "AYE" << '\n';
        else cout << "NAY" << '\n';
    }
    return 0;
}

by SakurajiamaMai @ 2024-07-11 20:56:59

这是去重的, 也就是AC的

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10, mod = 1e9 + 7;
struct node{
    int u, w;
};
vector<node> g[N];
int sz[N], dp[N], dist[N], wait[N], ok[N];
int now, Tsize, cnt, k, res, n, m;
bool vis[N];
void dfs1(int u, int fa){
    sz[u] = 1, dp[u] = 0;
    for(auto it : g[u]){
        int x = it.u;
        if(x == fa || vis[x]) continue;
        dfs1(x, u);
        sz[u] += sz[x];
        dp[u] = max(dp[u], sz[x]); 
    }
    dp[u] = max(dp[u], Tsize - sz[u]);
    if(dp[u] < dp[now]) now = u;
}
void dfs2(int u, int fa, int d){
    dist[++cnt] = d;
    for(auto it : g[u]){
        int x = it.u, w = it.w;
        if(x == fa || vis[x]) continue;
        dfs2(x, u, d + w);
    }
}
void dfs3(int u, int d, bool f){
    cnt = 0, dfs2(u, 0, d);
    sort(dist + 1, dist + 1 + cnt);
    for(int j = 1; j <= m; j++){
        for(int i = 1; i < cnt; i++){
            int x = lower_bound(dist + i + 1, dist + 1 + cnt, wait[j] - dist[i]) - dist;
            if(x && x <= cnt && dist[x] + dist[i] == wait[j] && x != i){
                if(f) ok[j] ++;
                else ok[j] --;
            }
        }
    }
}
void dfs(int u){
    dfs3(u, 0, true), vis[u] = true;
    for(auto it : g[u]){
        int x = it.u, w = it.w;
        if(vis[x]) continue;
        dfs3(x, w, false);
        now = 0, Tsize = sz[x], dfs1(x, 0);
        dfs(now);
    }
}
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c}), g[b].push_back({a, c});
    }
    for(int i = 1; i <= m; i++) cin >> wait[i];
    dp[now = 0] = 1e9, Tsize = n, dfs1(1, 0);
    dfs(now);
    for(int i = 1; i <= m; i++){
        if(ok[i]) cout << "AYE" << '\n';
        else cout << "NAY" << '\n';
    }
    return 0;
}

by _zuoqingyuan @ 2024-07-11 21:10:55

如果不进行所谓“去重”，就会把蓝色路径统计进去，实际上蓝色路径是不合法的，

by _zuoqingyuan @ 2024-07-11 21:11:16

@SakurajiamaMai

by SakurajiamaMai @ 2024-07-11 21:20:43

@_zuoqingyuan 多谢,懂了,之前一直对同一子树内的路径不合法很模糊,这下明白了!