[POI2008] STA-Station (学学换根dp)

题目 题意: 给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 一个结点的深度之定义为该节点到根的简单路径上边的数量。 思路: 换根dp. 1.先以任意一个点为根dfs1，求出f[root]。 2.考虑换根。看由u换成其子节点j之后的影响，进行dfs2。 从而在O(n)的时间内完成换根，得到。 f[j] = f[u] - s[j] + n - s[j] 时间复杂度: O(n) 代码:

// Problem: P3478 [POI2008] STA-Station
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3478
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i