Codeforces 1004E(树的直径+单调队列滑动窗口)

发表于 | 分类于 | | + s

Codeforces 1004E
题意：一棵$n$个点的树，你需要选出一条不超过$k$长度的链，使得其他所有点到链上的最短距离的最长距离最短。

这个有点像二分，但是并不好做。我们想到树的直径的性质，一棵树以直径中心为根子树深度最小。
考虑边权全是1的情况，选择的链一定在直径中间$k$长度的链。根据一棵树以直径中心为根子树深度最小性质很好证明。
现在有边权，那么就要找一个加权的直径，并且链也不在中间了。但是还在直径上。我们预处理出以下的信息：

$d1(u)$，直径上第$u$个点到左端点的距离
$d2(u)$，直径上第$u$个点的枝叶最长深度距离
$dl$，直径的带权长
$a(i)$，直径上的点从左到右的序号

求直径两遍 BFS，然后用 Dinic 分层图思想找出直径上的点。即找到一个任意点的最远点之后，找这个最远点的最远点时候顺便对于每个点分层，然后再从这个最远点往回一层一层地走必然能找到直径。对于$d1​$，顺便求出即可。$d2​$，DFS 求每个直径点往下枝叶最大深度即可，注意不要走到直径上。

然后对于最后的答案就化作：
$ans=min(max(d1(max(i - k + 1, 0)), dl - d1(i), d2(i), d2(i-1),……,d2(i-k+1)))$
对于后面的$d2$，就是一个滑动窗口最大值，用单调队列维护即可。

知识点：1 树上的这些最优化问题和直径、重心、二分、DP有关。
2 单调队列很容易写错，是检查重点
3 从简单到复杂，从极端到一般的思维方法很重要

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 100000 + 5;

struct edge {int nxt, v, wi;} ed[MAXN * 2];

int n, k, dl, que[MAXN * 2], l, r; 
int en, hd[MAXN], dis[MAXN], vis[MAXN], a[MAXN], cnt, d2[MAXN], d1[MAXN];
std::queue<int > q;
std::queue<std::pair<int, int > > Q;

inline void ins(int x, int y, int w) {
    ed[++en] = (edge){hd[x], y, w}, hd[x] = en;
    ed[++en] = (edge){hd[y], x, w}, hd[y] = en;
}

void dfs(int u, int pa, int dep, int &sor) {
    d2[sor] = std::max(d2[sor], dep);
    for (int i = hd[u]; i > 0; i = ed[i].nxt) {
        edge &e = ed[i];
        if (e.v != pa && !vis[e.v]) dfs(e.v, u, dep + e.wi, sor);
    }
}

void clean() {
    en = 0, ms(hd, -1);
}
int solve() {
    clean();
    for (int u, v, d, i = 1; i < n; i++) scanf("%d%d%d", &u, &v, &d), ins(u, v, d);
    ms(dis, 0), q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (!dis[e.v] && e.v != 1) dis[e.v] = dis[u] + e.wi, q.push(e.v);
        }
    }
    int x = 1;
    for (int i = 2; i <= n; i++) if (dis[i] > dis[x]) x = i;

    ms(dis, 0), vis[x] = 1, Q.push(std::make_pair(x, 1));
    while (!Q.empty()) {
        std::pair<int, int > p = Q.front(); Q.pop();
        int u = p.first, no = p.second;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (!dis[e.v] && e.v != x) vis[e.v] = no + 1, dis[e.v] = dis[u] + e.wi, Q.push(std::make_pair(e.v, no + 1));
        }
    }
    x = 1;
    for (int i = 2; i <= n; i++) if (dis[i] > dis[x]) x = i;
    dl = dis[x], k = std::min(k, vis[x]);

    int rm = vis[x], now = x; a[++cnt] = x;
    while (rm > 1) {
        for (int i = hd[now]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (vis[e.v] == rm - 1) {
                now = e.v, rm--, a[++cnt] = now, d1[cnt] = d1[cnt - 1] + e.wi;
                break;
            }
        }
    }

    ms(vis, 0);
    for (int i = 1; i <= cnt; i++) vis[a[i]] = 1;

    for (int i = 1; i <= cnt; i++) dfs(a[i], 0, 0, i);

    int ans = 1000000000, l = 1, r = 0;
    for (int i = 1; i <= cnt; i++) {
        while (l <= r && que[l] < i - k + 1) l++;
        ans = std::min(ans, std::max(std::max(d2[que[l]], d1[std::max(i - k + 1, 0)]), dl - d1[i]));
        while (l <= r && d2[i] >= d2[que[r]]) r--;
        que[++r] = i;
    }
    printf("%d\n", ans);
    return 0;
}
int main() {
    scanf("%d%d", &n, &k), solve();
    return 0;
}
------ 本文结束 ------