P3478 [POI2008]STA-Station(换根dp）

 先选1为根节点跑一遍记录dfs找出其所有节点的深度
dp i 是以i 为根所有节点的深度之和 
我们可以对i的儿子以o1的时间计算出以其儿子为根的所有节点深度之和
dp[son]=dp[fa]-num[son]+n-num[son]
num是i子树的节点总数

const int MAX=1e6+10;
ll dp[MAX];
int cnt;
int head[MAX];
struct E{
int to,next,w;
}e[MAX<<1]; void add(int u,int v){ e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; } ll d[MAX]; ll num[MAX]; int n,m; ll dfs(int u,int fa,int dd){ num[u]=1; dp[1]+=dd; for(int i=head[u];~i;i=e[i].next){ int v=e[i

P3478 [POI2008]STA-Station(换根dp）最先出现在Python成神之路。