Visits: 451

CF516D Drazil and Morning Exercise

题意

• 给定一棵 $n$ 个点的树，边有边权。
• 定义 $f_x = \max_{i=1}^n \text{dist}(x,i)$。
• $q$ 次询问最大的满足 $\max_{x \in s} f_x – \min_{x \in s} f_x \le l$ 的连通块 $s$ 包含的点数。
• $n \le 10^5$，$q \le 50$。

题解

先把 $f$ 线性求出来，然后由大到小双指针扫一遍，发现只会合并，因此并查集维护连通性即可，时间复杂度 $\mathcal O(n \log n + qn\alpha(n))$。

代码

const int N = 1e5 + 7;
int n, q, fa[N], s[N], v[N], ans;
ll m, f[N][2], g[N];
pair< ll, int > p[N];
vector< pi > e[N];

void dfs1(int x, int fa) {
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i].fi;
        if (y == fa) continue;
        dfs1(y, x);
        ll z = f[y][0] + e[x][i].se;
        if (z > f[x][1]) f[x][1] = z;
        if (z > f[x][0]) swap(f[x][0], f[x][1]);
    }
}

void dfs2(int x, int fa) {
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i].fi;
        if (y == fa) continue;
        int z = e[x][i].se;
        g[y] = max(g[x], f[y][0] + z == f[x][0] ? f[x][1] : f[x][0]) + z;
        dfs2(y, x);
    } 
}

int get(int x) {
    return x == fa[x] ? x : (fa[x] = get(fa[x]));
}

inline void merge(int x, int y) {
    if (x == y) return;
    if (s[x] > s[y]) swap(x, y);
    fa[x] = y, s[y] += s[x];
    ans = max(ans, s[y]);
}

int main() {
    rd(n);
    for (int i = 1, x, y, z; i < n; i++)
        rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) p[i] = mp(max(f[i][0], g[i]), i);
    sort(p + 1, p + n + 1);
    reverse(p + 1, p + n + 1);
    rd(q);
    while (q--) {
        rd(m), ans = 1;
        for (int i = 1; i <= n; i++) fa[i] = i, s[i] = 1, v[i] = 0;
        for (int l = 1, r = 0; l <= n; l++) {
            while (r < n && p[l].fi - p[r+1].fi <= m) {
                int x = p[++r].se;
                v[x] = 1;
                for (ui i = 0; i < e[x].size(); i++) {
                    int y = e[x][i].fi;
                    if (v[y]) merge(get(x), get(y));
                }
            }
            --s[get(p[l].se)], v[get(p[l].se)] = 0;
        }
        print(ans);
    }
    return 0;
}