HDU 6613 Squrirrel【树形DP + 换根】

题意：给你一棵树，你可以把某条边的边权变为0，然后选一个点，使得所有点到这个点的距离和最小。

思路：之前做过一道题没有变为0的操作，那道题直接求直径就可以，这道题比较麻烦，网上看了半天，，，

首先我们先dfs一遍求出来点1的答案，设dp[i][0][1]为以i为根的最长路径的最小长度，考虑对于相邻两个点u, v ， 我们可能会删除u, v 之间的边或者之前就将边删除了然后加上w[u][v]，所以dp[u][0][1] = min(dp[v][0][0], max(dp[v][0][1], dp[v][1][0]) + w[u][v])。

接着我们考虑换根的影响，用f[i][2] 记录一下当前节点与父节点间在哪删除边的答案，f[i][0]是来源于i的父节点方向最长距离和父节点的子树的最长距离取max再加上i和父节点的边权。如果次长距离是点i的话我们就需要维护第三长的距离。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1|1
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
vector<pair<int, int> > e[maxn]; //邻接点，权值
pair<int, int> dp[maxn][3][2]; //dp[i][j][k]：i：以i为根 ，j：0表示最长  1表示次长 2表示第3长 ，k：1带修改 0不带修改
int f[maxn][2], d[maxn]; //f[i][2]表示父节点换根的最大路径长度(修改/不修改)
int ans, id;

void init(int n)
{
    ans = inf, id = n;
    for(int i = 1; i <= n; ++i)
    {
        e[i].clear();
        memset(dp[i], 0, sizeof(dp[i])); //first是答案，second是结点
        memset(f[i], 0, sizeof(f[i]));
        d[i] = 0;
    }
}
void dfs(int u, int fa)
{
    for(auto x : e[u])
    {
        int v = x.first;
        if(v == fa) continue;
        dfs(v, u);
        d[v] = x.second;
        if(dp[v][0][0].first + d[v] >= dp[u][0][0].first) //维护三个最大
        {
            dp[u][2][0] = dp[u][1][0];
            dp[u][1][0] = dp[u][0][0];
            dp[u][0][0] = make_pair(dp[v][0][0].first + d[v], v);
        }
        else if(dp[v][0][0].first + d[v] >= dp[u][1][0].first)
        {
            dp[u][2][0] = dp[u][1][0];
            dp[u][1][0] = make_pair(dp[v][0][0].first + d[v], v);
        }
        else if(dp[v][0][0].first + d[v] >= dp[u][2][0].first)
            dp[u][2][0] = make_pair(dp[v][0][0].first + d[v], v);
    }
    int v = dp[u][0][0].second; //更新带修改的值
    dp[u][0][1].first = min(dp[v][0][0].first, max(dp[v][0][1].first, dp[v][1][0].first) + d[v]);
    v = dp[u][1][0].second;
    dp[u][1][1].first = min(dp[u][0][0].first, max(dp[v][0][1].first, dp[v][1][0].first) + d[v]);
}
void dfs2(int u, int fa) //换根
{
    int tmp1 = max(dp[u][0][1].first, dp[u][1][0].first), tmp2 = max(dp[u][0][0].first, f[u][1]);
    int res = min(max(tmp1, f[u][0]), tmp2);
    if(res < ans)
        ans = res, id = u;
    else if(res == ans)
        id = min(id, u);
    for(auto x : e[u])
    {
        int v = x.first;
        if(v == fa) continue;
        if(v == dp[u][0][0].second)
        {
            f[v][0] = max(dp[u][1][0].first, f[u][0]) + x.second;
            f[v][1] = min(max(dp[u][1][0].first, f[u][0]), min(max(f[u][0], max(dp[u][1][1].first, dp[u][2][0].first)), max(dp[u][1][0].first, f[u][1])) + x.second);
        }
        else
        {
            f[v][0] = max(dp[u][0][0].first, f[u][0]) + x.second;
            if(dp[u][1][0].second == v) //如果修改同一个地方
                f[v][1] = min(max(dp[u][0][0].first, f[u][0]), min(max(f[u][0], max(dp[u][0][1].first, dp[u][2][0].first)), max(dp[u][0][0].first, f[u][1])) + x.second);
            else
                f[v][1] = min(max(dp[u][0][0].first, f[u][0]), min(max(f[u][0], max(dp[u][0][1].first, dp[u][1][0].first)), max(dp[u][0][0].first, f[u][1])) + x.second);
        }
        dfs2(v, u);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        init(n);
        for(int i = 1; i < n; ++i)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            e[u].push_back({v, w});
            e[v].push_back({u, w});
        }
        dfs(1, -1);
        ans = max(dp[1][0][1].first, dp[1][1][0].first);
        dfs2(1, -1);
        printf("%d %dn", id, ans);
    }
    return 0;
}

最后

以上就是美好戒指最近收集整理的关于HDU 6613 Squrirrel【树形DP + 换根】的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。