换根DP

换根dp的通法：1.第一次扫描时，任选一个点为根，在“有根树”上执行一次树形DP，也就在回溯时发生的，自底向上的状态转移。

2.第二次扫描时,从刚才选出的根出发，对整棵树执行一次dfs，在每次递归前进行自上向下的推导，计算出换根后的解。

例题POJ3585 Accumulation Degree

dp[i]以i为根的子树中，把i作为源点的最大流量

转移$dp[x]=sum_{yepsilon son(x)}^{}left{egin{matrix}

min(dp[y],len[p]) & du[y]>1
len[p]& du[y]=1
end{matrix} ight.$

f[i]表示以i为源点的最大流量。

转移：$f[y]=dp[y]+left{egin{matrix}

min(f[x]-min(dp[y],len[p]),len[p]) & du[x]>1
len[p]& du[x]=1
end{matrix} ight.$

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxm=2e5+7;
int t,n;
int last[maxm],other[maxm+maxm],len[maxm<<1],pre[maxm<<1],l;
int dp[maxm];//以i为根的子树中，把i作为源点的最大流量
int f[maxm];//以i为源点的最大流量 
int du[maxm];
void add(int x,int y,int z)
{
 l++;
 pre[l]=last[x];
 last[x]=l;
 other[l]=y;
 len[l]=z;	
}
void dfs(int x,int fa)
{
  for(int p=last[x];p;p=pre[p])
  {
    int v=other[p];
	if(v==fa) continue;
	dfs(v,x);
	if(du[v]!=1)dp[x]+=min(dp[v],len[p]);
	if(du[v]==1) dp[x]+=len[p];	
  }
}
void dfs1(int x,int fa)
{
 for(int p=last[x];p;p=pre[p])
 {
  int v=other[p];
  if(v==fa) continue;
  if(du[x]==1)
  f[v]=dp[v]+len[p];
  else f[v]=dp[v]+min(f[x]-min(dp[v],len[p]),len[p]);//f[x]-min(dp[v],len[p])为x流向其他部分的流量 
  dfs1(v,x);
 }
}
int main()
{
 scanf("%d",&t);
 while(t--)
 {
  memset(last,0,sizeof(last));
  l=0;
  memset(du,0,sizeof(du));
  memset(dp,0,sizeof(dp));
  scanf("%d",&n);
  for(int i=1;i<=n-1;i++)
  {
   int x,y,z;
   scanf("%d%d%d",&x,&y,&z);
   add(x,y,z);
   add(y,x,z);
   du[x]++;
   du[y]++;
  }
  dfs(1,0);//先以1为根
  f[1]=dp[1];
  dfs1(1,0);
  int ans=0;
  for(int i=1;i<=n;i++)
  ans=max(ans,f[i]);
  printf("%d
",ans); 
 }
 return 0;	
}

练习1.STA-Station

记录一个子树大小，转移时记得消除dep的影响即可

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxm=2e6+7;
int n;
int pre[maxm],last[maxm],l,other[maxm];
ll dp[maxm],dp1[maxm];
ll dep[maxm];
int size[maxm];
void add(int x,int y)
{
 l++;
 pre[l]=last[x];
 last[x]=l;
 other[l]=y;
}
void dfs(int x,int fa)
{
 dep[x]=dep[fa]+1;
 dp[x]=dep[x];
 size[x]=1;
 for(int p=last[x];p;p=pre[p])
 {
   int v=other[p];
   if(v==fa) continue;
   dfs(v,x);
   dp[x]+=dp[v];
   size[x]+=size[v];
 }
}
void dfs1(int x,int fa)
{
  for(int p=last[x];p;p=pre[p])
  {
   int v=other[p];
   if(v==fa) continue;
   int tmp=dp[v]-size[v]*dep[v];
   dp1[v]=tmp+dp1[x]-tmp-size[v]+size[1]-size[v];
   dfs1(v,x);	
  }
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n-1;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  add(x,y);
  add(y,x);
 }
 dep[0]=-1;
 dfs(1,0);
 dp1[1]=dp[1];
 dfs1(1,0);
 ll ans=0;
 int pos=1;
 for(int i=1;i<=n;i++)
 {
   if(dp1[i]>ans)
   {
   	ans=dp1[i];
   	pos=i;
   }
 }
 printf("%d
",pos);
 return 0;	
}