HDU多校第九场 1007 Rikka with Travels —— 树形DP + 换根

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

题目大意：

    一棵无根树，定义 $L(a,b)$ 为树上从 $a$ 到 $b$ 的路径点数
    计算 $pairs(l_1,l_2)$ ，$L(a,b)=l_1,L(c,d)=l_2$
    且从 $a$ 到 $b$ 的路径与 $c$ 到 $d$ 的路径不相交

解题思路：

    计算 $pairs(l_1,l_2)$，发现若满足 $pair(x,y)$
    则也满足 $pairs(i,y)，i\in (1,x)$
    则只需要求出对于每个 $x$，最大的 $y$ 即可
    然后 $mx[i]=max(mx[i],mx[i+1])$，则可以 $O(n)$ 计算答案

    考虑路径不相交，则可以枚举边，用这条边去分割这棵树
    然后计算两颗子树的直径 $x$ 和 $y$，对应上面
    计算子树直径可以直接用树形$DP$，$dp[rt][0]$ 表示 $rt$ 的最大深度
    $dp[rt][1]$ 表示 $rt$ 的最大直径，则选取子树内最大的两个 $dp[son][0]$ 更新即可

    然后考虑怎么枚举边，思考在换根$dp$中，从父亲 $rt$ 换到 $son$ 的时候
    首先要删除 $rt$ 到 $son$ 的边，更新 $rt$ 的信息，在这个时候就达到了枚举边的目的
    也就是在换根过程中直接计算答案即可
    换根类似题：HDU多校第八场 1006 Acesrc and Travel —— 树形DP + 换根

核心：树形DP + 换根（枚举边）

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
#define x first
#define y second
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 1e5 + 5;
int T, n, dp[maxn][2], mx[maxn];
vector <int> g[maxn];
map <pii, int> m[maxn][2];
map <pii, int>::iterator it;inline void add0(int u, int v){m[u][0][{dp[v][0], v}]++;while(m[u][0].size()>3) m[u][0].erase(m[u][0].begin());
}
inline void add1(int u, int v){m[u][1][{dp[v][1], v}]++;while(m[u][1].size()>3) m[u][1].erase(m[u][1].begin());
}inline void get(int rt){dp[rt][0] = dp[rt][1] = 1;if(m[rt][0].size()){it = m[rt][0].end(), --it;dp[rt][0] = dp[rt][1] = it->x.x + 1;if(m[rt][0].size() > 1){int tmp = it->x.x;--it;dp[rt][1] = max(dp[rt][1], tmp + it->x.x + 1);}}if(m[rt][1].size()){it = m[rt][1].end(), --it;dp[rt][1] = max(dp[rt][1], it->x.x);}
}inline void dfs(int u, int fa){m[u][0].clear(), m[u][1].clear();for(auto v : g[u]){if(v == fa) continue;dfs(v, u);add0(u, v);add1(u, v);}get(u);
}inline void gao(int x, int y){mx[x] = max(mx[x], y);mx[y] = max(mx[y], x);
}inline void move(int rt, int son){m[rt][0].erase( {dp[son][0], son} );m[rt][1].erase( {dp[son][1], son} );get(rt);gao(dp[rt][1], dp[son][1]);add0(son, rt);add1(son, rt);get(son);
}inline void dfs1(int rt, int fa){for(auto son : g[rt]){if(son == fa) continue;move(rt, son);dfs1(son, rt);move(son, rt);}
}int main() {scanf("%d", &T);while(T--){scanf("%d", &n);memset(mx, 0, sizeof(mx));for(int i=1; i<=n; i++) g[i].clear();for(int i=1, u, v; i<n; i++){scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);dfs1(1, 0);ll ans = 0;for(int i=n; i; i--) mx[i] = max(mx[i], mx[i+1]), ans += mx[i];printf("%lld\n", ans);}
}