HDU - 6613 Squrirrel

题意：

给定一棵有 $n$ 个结点的树，边带权，现在可以选择一条边权置 $0$，求一个结点作为根，使得叶结点最大深度最小。$(n\le 2\times 10^5)$

链接：

https://vjudge.net/problem/HDU-6613

解题思路：

考虑没有边权置 $0$ 操作，很容易写出树形 $dp$ 的转移式。现在考虑可以将一条边权置 $0$，则 $dp$ 数组多开一维，代表是否做了删边操作，$dp[1]$ 表示对应子树内做删边操作后的最大深度。$u$ 到 $v$ 换根 $dp$ 时有三种删边的情况：① 删 $w(u,v)$；② 在 $v$ 的兄弟结点对应子树内删；③ 在 $u$ 往父结点方向的子树内删。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
vector<pii> G[maxn];
int mx[maxn][2], mx2[maxn][2], mx3[maxn][2], fmx[maxn][2];
int pmx[maxn], pmx2[maxn], wi[maxn];
int n;
void dfs1(int u, int f){
mx[u][0] = mx[u][1] = mx2[u][0] = mx2[u][1] = mx3[u][0] = mx3[u][1] = 0;
pmx[u] = pmx2[u] = 0;
for(auto &e : G[u]){
int v = e.second, w = e.first;
if(v == f) continue;
dfs1(v, u);
int d = mx[v][0] + w;
wi[v] = w;
if(d > mx[u][0]){
mx3[u][0] = mx2[u][0];
mx2[u][0] = mx[u][0], pmx2[u] = pmx[u];
mx[u][0] = d, pmx[u] = v;
}
else if(d > mx2[u][0]){
mx3[u][0] = mx2[u][0];
mx2[u][0] = d, pmx2[u] = v;
}
else if(d > mx3[u][0]){
mx3[u][0] = d;
}
}
int v = pmx[u], w = wi[v];
mx[u][1] = min(mx[v][0], max(mx[v][1], mx2[v][0]) + w);
v = pmx2[u], w = wi[v];
mx2[u][1] = min(mx[v][0], max(mx[v][1], mx2[v][0]) + w);
}
void dfs2(int u, int f){
for(auto &e : G[u]){
int v = e.second, w = e.first;
if(v == f) continue;
if(v == pmx[u]){
fmx[v][0] = max(fmx[u][0], mx2[u][0]) + w;
int d1 = max(fmx[u][0], mx2[u][0]);
int d2 = max(fmx[u][1], mx2[u][0]) + w;
int d3 = max(fmx[u][0], max(mx2[u][1], mx3[u][0])) + w;
fmx[v][1] = min(min(d1, d2), d3);
}
else if(v == pmx2[u]){
fmx[v][0] = max(fmx[u][0], mx[u][0]) + w;
int d1 = max(fmx[u][0], mx[u][0]);
int d2 = max(fmx[u][1], mx[u][0]) + w;
int d3 = max(fmx[u][0], max(mx[u][1], mx3[u][0])) + w;
fmx[v][1] = min(min(d1, d2), d3);
}
else{
fmx[v][0] = max(fmx[u][0], mx[u][0]) + w;
int d1 = max(fmx[u][0], mx[u][0]);
int d2 = max(fmx[u][1], mx[u][0]) + w;
int d3 = max(fmx[u][0], max(mx[u][1], mx2[u][0])) + w;
fmx[v][1] = min(min(d1, d2), d3);
}
dfs2(v, u);
}
}
int cal(int u){
return min(max(fmx[u][0], max(mx[u][1], mx2[u][0])), max(fmx[u][1], mx[u][0]));
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; ++i){
G[i].clear();
}
for(int i = 1; i < n; ++i){
int u, v, w; cin >> u >> v >> w;
G[u].pb({w, v}), G[v].pb({w, u});
}
dfs1(1, 0), dfs2(1, 0);
// for(int i = 1; i <= n; ++i){
//
cout << i << " " << mx[i][1] << " " << mx2[i][1] << endl;
// }
int ret1 = 0, ret2 = inf;
for(int i = 1; i <= n; ++i){
int tmp = cal(i);
if(!ret1 || tmp < ret2) ret1 = i, ret2 = tmp;
}
cout << ret1 << " " << ret2 << endl;
}
return 0;
}

最后

以上就是彩色魔镜为你收集整理的HDU - 6613 Squrirrel的全部内容，希望文章能够帮你解决HDU - 6613 Squrirrel所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。