• https://www.luogu.com.cn/problem/P3629

求两次直径的高级做法好像已经烂大街了。。
这里贴一下更常规的换根 dp。。

做法就是 Two Paths 多考虑一种情况即可~~

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(3e5) + 9;

int dn[N], up[N]; // 子树内直径，子树外直径
int d[N][4], e[N]; // 子数内 top4 最长距离，子树外最长距离
VI adj[N]; int n, K, z;

void upd(int d[], int v) {
    if (v > d[0]) d[3] = d[2], d[2] = d[1], d[1] = d[0], d[0] = v;
    else if (v > d[1]) d[3] = d[2], d[2] = d[1], d[1] = v;
    else if (v > d[2]) d[3] = d[2], d[2] = v;
    else if (v > d[3]) d[3] = v;
}

void dfs1(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        dfs1(v, u);
        upd(d[u], d[v][0] + 1);
        checkMax(dn[u], dn[v]);
    }
    checkMax(dn[u], d[u][0] + d[u][1]);
}

void dfs2(int u = 1, int p = 0) {
    for (auto v: adj[u]) if (v != p) {
        checkMax(up[v], up[u]);
        checkMax(e[v], e[u] + 1);
        int t = d[v][0] + 1;
        if (d[u][0] == t) {
            checkMax(up[v], d[u][1] + d[u][2]);
            checkMax(up[v], d[u][1] + e[u]);
            checkMax(e[v], d[u][1] + 1);
        }
        else {
            if (d[u][1] == t) checkMax(up[v], d[u][0] + d[u][2]);
            else checkMax(up[v], d[u][0] + d[u][1]);
            checkMax(up[v], d[u][0] + e[u]);
            checkMax(e[v], d[u][0] + 1);
        }
        dfs2(v, u);
    }

    if (K == 2) checkMax(z, dn[u] + up[u]);
    upd(d[u], e[u]); checkMax(z, d[u][0] + d[u][1] + (K == 2 ? d[u][2] + d[u][3] : 0));
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n, K); DO(n-1) {
        int x, y; RD(x, y);
        adj[x].PB(y);
        adj[y].PB(x);
    }

    dfs1(); dfs2();
    cout << 2*(n-1) - z + K << endl;
}

Posted by xiaodao
Category: 日常