欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Luogu P4115Qtree4 P2056[ZJOI2007]捉迷藏 题解

程序员文章站 2022-05-12 15:19:16
...

题目链接

[ZJOI2007]捉迷藏
P4115 Qtree4

题解
动态点分治+堆

点分树 : 我们把分治过程中遍历过的重心都连起来 上一层的重心连接下一层的重心 可以得到一棵新的树

然后在这颗树上乱搞

先对于每个点弄两个大根堆

q1[x] 存x的所有白点后代到x的父亲 的原树上的距离
q2[x] 存x的每个子树中到x 的原树上的最大距离

显然, q2为x所有儿子q1的根节点

然后再弄一个大根堆存答案 显然为每个节点q2的 最大值+次大值

考虑每次更新一个点, 我们只需要从这个点不断向上更新(在点分树上)

删除 : 再记一个标记堆, 操作时对比下当前两个堆的堆顶是否相等
添加就没什么好说的

代码复杂,先坑一个50分暴力点分治

#include<bits/stdc++.h>

using namespace std;

inline int gi() {
    int f = 1, s = 0;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') f = -1, c = getchar();
    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();
    return f == 1 ? s : -s;
}
const int N = 100010;

struct node {
    int to, next;
}g[N<<1];
int last[N], gl;

void add(int x, int y) {
    g[++gl] = (node) {y, last[x]};
    last[x] = gl;
    g[++gl] = (node) {x, last[y]};
    last[y] = gl;
    return ;
}

bool c[N];
int sum, f[N], siz[N], rt;
bool vis[N];


void getroot(int u, int fa) {
    siz[u] = 1; f[u] = 0;
    for (int i = last[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == fa || vis[v]) continue;
        getroot(v, u);
        siz[u] += siz[v];
        f[u] = max(siz[v], f[u]);
    }
    f[u] = max(f[u], sum-siz[u]);
    if (f[u] < f[rt]) rt = u;
    return ;
}
int ans, cnt;

int dfs(int u, int d, int fa) {
    int ans = -1000000000;
    if (!c[u]) ans = d;
    for (int i = last[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == fa) continue;
        ans = max(ans, dfs(v, d+1, u));
    }
    return ans;
}
int MAX[N];
void solve(int u) {
    vis[u] = 1;
    if (!c[u]) MAX[u] = 0, ans = max(ans, 0);
    else MAX[u] = -1000000000;
    for (int i = last[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (vis[v]) continue;
        int s = dfs(v, 1, u);
        ans = max(ans, MAX[u]+s);
        MAX[u] = max(MAX[u], s);
        rt = 0; sum = siz[v];
        getroot(v, 0);
        solve(v);
    }
    return ;
}

int main() {
    int n = gi();
    for (int i = 1; i < n; i++)
        add(gi(), gi());
    int m = gi();
    while (m--) {
        char s;
        cin>>s;
       	if (s == 'C')
            c[gi()] ^= 1;
        else {
            memset(vis, 0, sizeof(vis));
            sum = f[0] = n; rt = 0;
            ans = -1;
            getroot(1, 0);
            solve(rt);
            printf("%d\n", ans);
        }
    }
    return 0;
}

相关标签: 点分治