[BZOJ3611] [Heoi2014]大工程（DP + 虚树）

传送门

$dp[i][0]$表示节点i到子树中的所有点的距离之和

$dp[i][1]$表示节点i到子树中最近距离的点的距离

$dp[i][2]$表示节点i到子树中最远距离的点的距离

建好虚树后dp即可。

因为对于虚树掌握的还不是很熟，有些细节还是要注意。

虚树中可能会加入一些lca节点，这些节点在dp的时候是不应该统计的。

对于本题来说，别忘记考虑某一节点不同子树中点对的组合。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 2000010#define LL long longusing namespace std;LL ans1, ans2, dp[N][3];int n, cnt, rp, m, top, T;int head[N], to[N], nex[N], val[N], dis[N], size[N], dfn[N], deep[N], f[N][21], q[N], s[N], flag[N];inline int read()inline void add(int x, int y)inline void dfs1(int u)}head[u] = 1;}inline int calc_lca(int x, int y)inline bool cmp(int x, int y)inline void dfs2(int u)if(flag[u])head[u] = 1;}inline void solve()lca = calc_lca(s[top], q[i]);while(dfn[lca] < dfn[s[top]])add(s[top  1], s[top]), top;}s[++top] = q[i];}while(top > 1) add(s[top  1], s[top]), top;ans2 = 0;ans1 = 1ll * 1e9 * 1e9;dfs2(s[1]);printf("%lld %lld %lld\n", dp[s[1]][0], ans1, ans2);for(i = 1; i <= m; i++) flag[q[i]] = 0;}int main()dfs1(1);T = read();while(T) solve();return 0;}

上一篇：[luoguP1963] [NOI2009]变换序列（二分图最大匹配）

下一篇：[luoguP3231] [HNOI2013]消毒（最小点覆盖 + 状压）