HDU多校第三场1011 Squrirrel —— 换根 + 树形DP

题目链接：点我啊╭(╯^╰)╮

题目大意：

    在一棵无根树上，有边权，可以将某一条边的边权置 $0$     问最坏情况下，从某个结点出发到最远结点的距离最小的是多少？？？

解题思路：

    设 $dp[rt][0]$ 为不让边权置 $0$，以 $rt$ 为根到子树结点的最远距离     则 $dp[rt][1]$ 为让一条边权置 $0$，以 $rt$ 为根到子树结点的最远距离     $se[rt][0]$ 为第二远，表示相同

    $dp[rt][0]=max(dp[rt][0],dp[son][0]+w)$     若 $son$ 为 $dp[rt][0]$ 的决策点，则 $dp[rt][1]$ 肯定与 $son$ 相关：     $dp[rt][1]=max(se[rt][0],min(dp[son][0],dp[son][1]+w))$

    要求最坏情况下距离最小，只需要保证不置 $0$的距离最大的同时，置 $0$的距离距离尽量小

---

    考虑换根，因为每个节点只保存了到子树的信息     所以从一个根换到另一个根，只需要改变这两个结点的信息即可

    结构体 $node$ 表示以 $id$ 为为儿子，$dp0$为不置 $0$，$dp1$为置 $0$的信息     利用 $map<node,int>m[maxn]$ 排好序     从 $rt$ 换到 $son$，将 $m[rt]$ 指向 $son$ 儿子的信息删掉     同时 $m[son]$ 要加上指向 $rt$ 为儿子的信息

    注意这里需要删掉信息，同时需要维护前两远的信息，因此需要维护前三远的信息

---

    由于换根利用到了 $map$，常数比较大，可以用 $vector$ 手动 $sort$     或者直接用数组手动比较，但 $map$ 写的确实方便     下面总结了针对的卡常技巧：     ①：inline     ②：控制 $map$ 大小：while(m[rt].size()>3) m[rt].erase(--m[rt].end());     ③：采用 爆炸输入输出挂~~~     ④：多交几十发     ⑤：改vector

---

    本题必须采用 ① 和 ②，不加爆炸输入挂的话有百分之十的几率可以卡到 $3900ms$     加了爆炸输入挂稳定在 $3000ms$     考虑这题是多组并且是在 $HDU$ 上，说明常数的控制还是比较客观的     实在不行在换 $vector$ 吧

---

    本题提供了一种模板，可以说是一种惯用写法     会陆续更新一些套用本模板的换根 $DP$     这类题都可以用数组的形式去写，只不过要多几十行代码     $PS：$我不是这套模板的原创作者

核心：利用子树信息换根

这里的代码没有加入 爆炸输入输出挂~~~

#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; using pii = pair <int,int>; const int maxn = 2e5 + 5; int T, n, dp[maxn][2], ans, pos; vector <pii> g[maxn]; struct node{ int dp0, dp1, id; bool operator < (const node &A)const { if(dp0 ^ A.dp0) return dp0 > A.dp0; if(dp1 ^ A.dp1) return dp1 < A.dp1; return id < A.id; } }; map <node, int> m[maxn]; map <node, int>::iterator it; inline void get(int rt){ if(m[rt].size() == 0){ dp[rt][0] = dp[rt][1] = 0; return; } it = m[rt].begin(); int dp1 = it->fi.dp1; dp[rt][0] = it->fi.dp0; dp[rt][1] = max(dp1, (++it)->fi.dp0); while(m[rt].size()>3) m[rt].erase(--m[rt].end()); } inline void dfs1(int u, int fa){ for(auto v : g[u]){ if(v.fi == fa) continue; dfs1(v.fi, u); int dp0 = dp[v.fi][0] + v.se; int dp1 = min(dp[v.fi][0], dp[v.fi][1] + v.se); m[u][ {dp0, dp1, v.fi} ]++; } get(u); } inline void move(int rt, int son, int w){ m[rt].erase( {dp[son][0] + w, min(dp[son][0], dp[son][1] + w), son} ); get(rt); m[son][ {dp[rt][0] + w, min(dp[rt][0], dp[rt][1] + w), rt} ]++; get(son); } inline void dfs2(int u, int fa){ if(ans > dp[u][1]){ ans = dp[u][1]; pos = u; } for(auto v : g[u]){ if(v.fi == fa) continue; move(u, v.fi, v.se); dfs2(v.fi, u); move(v.fi, u, v.se); } } int main() { scanf("%d", &T); while(T--){ ans = 2e9; scanf("%d", &n); for(int i=1; i<=n; i++) g[i].clear(), m[i].clear(); for(int i=1, u, v, w; i<n; i++){ scanf("%d%d%d", &u, &v, &w), g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs1(1, 0); dfs2(1, 0); printf("%d %d\n", pos, ans); } }