题解 CF516D 【Drazil and Morning Exercise】

· · 题解

标签: 图论, 并查集

注意这个 f 的定义是对于全局的, 而不是对于某个连通块, 这里搞错了就不是同一道题了(或许只有我搞错了吧).

Part 1

首先两遍 dfs 求出每个点的 f . 任意选定一个点作为根, 第一遍 dfs 求出每个点到子树内最远的距离, 第二遍 dfs 用父亲更新儿子. 实现很简单, 不赘述, 可以看看代码.

Part 2

观察发现距离某个点最远的点组成的点集必然包含每一条直径的两个端点中至少一个. 所以显然以任意一条直径的中点作为树根, 每一个点的 f 都不比其子树内的点的 f 大.

根据这个单调性我们可以用尺取(也即 two points)来做了. 

#include <bits/stdc++.h>
using namespace std;
long long read();
void chmax(long long &x, long long y) { x < y ? x = y : x; }
int n, q;
struct E {
    int v, w;
};
vector<E> e[200005];
void add(int f, int t, int w) {
    e[f].push_back((E){t, w}), e[t].push_back((E){f, w});
}

long long f[200005], g[200005];

void update(int u, long long d) {
    chmax(g[u], d), (g[u] > f[u]) ? swap(g[u], f[u]) : void();
}

void dfs1(int u, int fa) {
    for (int i = 0, v; i < e[u].size(); ++i)
        if ((v = e[u][i].v) != fa) dfs1(v, u), update(u, f[v] + e[u][i].w);
}

int up[200005], p[200005];
bool cmp(int u, int v) { return f[u] == f[v] ? u < v : f[u] < f[v]; }
void dfs2(int u, int fa) {
    for (int i = 0, v; i < e[u].size(); ++i) {
        if ((v = e[u][i].v) == fa) continue;
        update(v, e[u][i].w + ((f[v] + e[u][i].w == f[u]) ? g[u] : f[u]));
        dfs2(v, u);
    }
    for (int i = 0, v; i < e[u].size(); ++i)
        cmp(u, v = e[u][i].v) ? up[v] = u : up[u] = v;
}

int fa[200005], w[200005];
int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }

void work(long long d) {
    int res = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i, w[i] = 1;
    for (int i = n, j = n; i >= 1; --i) {
        while (f[p[j]] > f[p[i]] + d) --w[find(p[j--])];
        res = max(res, w[p[i]]), w[fa[p[i]] = up[p[i]]] += w[p[i]];
    }
    printf("%d\n", res);
}

int main() {
    n = read();
    for (int i = 1, u, v; i < n; ++i) u = read(), v = read(), add(u, v, read());
    dfs1(1, 0), dfs2(1, 0), q = read();
    for (int i = 1; i <= n; ++i) p[i] = i;
    sort(p + 1, p + 1 + n, cmp);
    while (q--) work(read());
    return 0;
}
const int _SIZE = 1 << 22;
char ibuf[_SIZE], *iS = ibuf, *iT = ibuf;
#define gc                                                         \
    (iS == iT ? iT = ((iS = ibuf) + fread(ibuf, 1, _SIZE, stdin)), \
     (iS == iT ? EOF : *iS++) : *iS++)
long long read() {
    long long x = 0, f = 1;
    char c = gc;
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = gc;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc;
    return x * f;
}