[CF1453E] Dog Snacks

[CF1453E] Dog Snacks - 树形dp

Description

给定一颗n个节点的树，从一号的出发要最终回到一号点，除了一号点，每个点都只能被访问一次，要做到能走就走，现在求单次步长最大的最小值

Solution

基本思路是，处理完一个子树以后，再去处理另一个子树

对每个结点，我们维护一个跳出距离，即进入这个子树后，最后退出时的最小距离，换句话说，其实就是到最近的叶子的距离

那么对于任意一个内部分支点，它对答案的贡献，就是其所有子树中最大的跳出距离 + 1

这里有的跳出距离充当的是在子树间横跳，有的是跳出整个子树，但无论如何，其贡献都可以这样表示

对于叶子，贡献自然为 0

对于根，比较特殊，由于最后不需要跳出去，所以不能按上面那样算，需要修正为，各个子树间，最大的跳出距离 和 次大的跳出距离 + 1 之间的较大值

对于只有一个孩子的内部点，不需要统计贡献

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;
vector<int> g[N];
int h[N];
vector<int> seq;
int ans = 0;

void dfs1(int p, int from)
{
    h[p] = 1e18;
    for (auto q : g[p])
    {
        if (q == from)
            continue;
        dfs1(q, p);
        h[p] = min(h[p], 1 + h[q]);
    }
    if (h[p] == 1e18)
        h[p] = 0;
}

void dfs2(int p, int from)
{
    int fir = 0, sec = 0;
    for (auto q : g[p])
    {
        if (q == from)
            continue;
        dfs2(q, p);
        if (h[q] + 1 >= fir)
        {
            sec = fir;
            fir = h[q] + 1;
        }
        else
        {
            if (h[q] + 1 > sec)
                sec = h[q] + 1;
        }
    }
    if (p != 1)
    {
        if (g[p].size() >= 3)
        {
            ans = max(ans, fir + 1);
        }
    }
    else
    {
        ans = max(ans, max(fir, sec + 1));
    }
}

void solve()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = 1; i <= n; i++)
        h[i] = 0;
    seq.clear();
    ans = 0;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs1(1, 0);

    dfs2(1, 0);

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}