题解 CF1294F【Three Paths on a Tree】

· · 题解

提供一种看上去比较直观但其他题解未提及的做法。

考虑从下到上的去对每个子树统计答案，最终取最大值即可。

定义：

$g(x)$ 为在 $x$ 的子树内选出两个最近公共祖先为 $x$ 的叶节点的最大访问路径数。 $f(x)$ 为在 $x$ 的子树中选择三个点，且三点的路径上包含 $x$ 的最大路径访问数。 转移方法： $h(x)=\max_{v\in subtree(x)} h(v)+1 g(x)=\max(\max_{v\in subtree(x)}g(v)+1,h1(x)+h2(x))

其中 h1(x), h2(x) 为 x 子节点中最大的两个 h 值。

f(x)=\max(\max_{v\in subtree(x)}f(v),h1(x)+h2(x)+h3(x),g1(x)+h1(x))

其中 h1(x), h2(x), h3(x), g1(x) 为 x 子结点中最大的三个 h 值和最大的 g 值。

若最大的 h, g 在同一子节点下时，特殊处理找次大的值。

方案的记录和转移一起进行。

当情况为以 1 为根的链时，在链上随便找一个非根非叶的点即可。

AC代码如下：

#include <bits/stdc++.h>
#define ls x << 1
#define rs x << 1 | 1
#define int long long
#define ll long long
#define rep(i,x,y) for(LL i=(x);i<=(y);i++)
#define per(i,x,y) for(LL i=(x);i>=(y);i--)
#define pb push_back
#define mp make_pair
#define vi vector<LL>
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
using namespace std;
const int N = 2000010;
const int mod = 998244353;
int n, f[N], g[N], hi[N], hx[N], pp[4]; vector<int> e[N];
struct node {int x, y;} gx[N];
struct nod {int x, y, z;} fx[N], anss;
void dfs1(int x, int fa) {
    if(e[x].size() == 1 && x != 1) {hi[x] = 0, hx[x] = x; return ;}
    for(int v : e[x]) {
        if(v != fa) {
            dfs1(v, x);//, hi[x] = max(hi[x], hi[v] + 1);
            if(hi[v] + 1 > hi[x]) hi[x] = hi[v] + 1, hx[x] = hx[v];
        }
    }
}
void dfs2(int x, int fa) {
    g[x] = hi[x], gx[x] = {hx[x], x}; vector<pii> h;
    for(int v : e[x]) {
        if(v != fa) {
            dfs2(v, x), h.pb(mp(hi[v] + 1, v));//g[x] = max(g[x], g[v] + 1);
            if(g[v] + 1 > g[x]) g[x] = g[v] + 1, gx[x] = gx[v];
        }
    }
    sort(h.begin(), h.end(), [&](pii x, pii y) {return x.fi > y.fi;});
    if(h.size() >= 2) {
        //g[x] = max(g[x], h[0] + h[1]);
        if(h[0].fi + h[1].fi > g[x]) g[x] = h[0].fi + h[1].fi, gx[x] = {hx[h[0].se], hx[h[1].se]};
    }
}
void dfs3(int x, int fa) {
    if(e[x].size() == 1 && x != 1) return ;
    vector<pii> h, gg; f[x] = g[x], fx[x] = {x, gx[x].x, gx[x].y};
    for(int v : e[x]) {
        if(v != fa) {
            dfs3(v, x), h.pb(mp(hi[v] + 1, v)), gg.pb(mp(g[v] + 1, v));//, f[x] = max(f[x], f[v]);
            if(f[v] > f[x]) f[x] = f[v], fx[x] = fx[v];
        }
    }
    sort(h.begin(), h.end(), [&](pii x, pii y) {return x.fi > y.fi;});
    sort(gg.begin(), gg.end(), [&](pii x, pii y) {return x.fi > y.fi;});
    // if(x == 3) cout << h.size() << endl;
    if(h.size() >= 3) {
        //f[x] = max(f[x], h[0].fi + h[1].fi + h[2].fi);
        if(h[0].fi + h[1].fi + h[2].fi > f[x]) 
            f[x] = h[0].fi + h[1].fi + h[2].fi, fx[x] = {hx[h[0].se], hx[h[1].se], hx[h[2].se]};
    }
    if(h[0].se == gg[0].se) {
        if(h.size() >= 2) {
            //f[x] = max(f[x], h[0].fi + gg[1].fi);
            if(h[0].fi + gg[1].fi > f[x]) f[x] = h[0].fi + gg[1].fi, fx[x] = {hx[h[0].se], gx[gg[1].se].x, gx[gg[1].se].y};
            //f[x] = max(f[x], h[1].fi + gg[0].fi);
            if(h[1].fi + gg[0].fi > f[x]) f[x] = h[1].fi + gg[0].fi, fx[x] = {hx[h[1].se], gx[gg[0].se].x, gx[gg[0].se].y};
        }
    }
    else if(h.size() >= 2) {
        //f[x] = max(f[x], h[0].fi + gg[0].fi);
        if(h[0].fi + gg[0].fi > f[x]) 
            f[x] = h[0].fi + gg[0].fi, fx[x] = {hx[h[0].se], gx[gg[0].se].x, gx[gg[0].se].y};
    }
}
void solve() {
    cin >> n; int ans = 0;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        e[u].pb(v), e[v].pb(u);
    }
    dfs1(1, 0), dfs2(1, 0), dfs3(1, 0);
    for(int i = 1; i <= n; i++) if(f[i] > ans) ans = f[i], anss = fx[i];
    cout << ans << endl;
    if(anss.x == anss.z) {
        for(int i = 1; i <= n; i++) if(i != anss.y && i != anss.x) {anss.z = i; break ;}
    }
    cout << anss.x << " " << anss.y << " " << anss.z << endl;
}
signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); 
    int T = 1; //cin >> T; cin.ignore();
    while(T--) solve();
    return 0;
}