树的最小距离和--题解 P1395 【会议】
这一题树上动态规划，是我首次自己搞出来的。
以为自己的不是正解，没想到跟正解截然无二
当然是定义f[i]=以i为根的最小距离和。
随便想想可以搞出， 一个状态是可以被任意一个相邻状态推出的。
设j与i相邻：
，size[]指去除<i,j>这条边（也就是删去j点）后有i的这个联通块的大小（节点个数）。
这个方程的意思是：
把树分为包含i一块，暂且称为i块；包含j一块，称为j块。
j块上的点到j的距离，和i块上的点到j的距离，构成了f[j].
如果把j挪到i上，j块上的点（共n-size[i]个）都需要再跑一步；而i块上的点（size[i]个），都可以少跑一步。类似于线段上取点使得距离和最小经典问题的思想？？
但是如果顺序杂乱无章，你就很不好记录size,也就无从转移。
根据树上动态规划的基本思路，我们想到钦定1为根，按照深度分块，size记录的也就是子树的大小了。
此时又有一个问题：是根转叶还是叶转根呢？我们发现，就算我们知道方程，知道size,第一个f[]的值还是得暴力算出来的。
当然，求诸叶不如求一根，那么思路就基本确定了：
1.DFs1():求出size,以及f[1].
2.DFs2():求出f[]数组其他值。
根据树的常识,以一个节点为根的距离和便是所有点深度的和。
但是这里开一个dep[]似乎有点浪费，于是我们有两个选择：一，是记录dep,DFs1返回size（当然，是不行的,size以后还要用）,二，
就是记录size,DFs1返回dep。
于是
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 50001
int n;
struct Edge{
int x,y,nxt;
}e[maxn<<1];
int in[maxn],tot;
inline void ins(int x,int y){
e[++tot].x=x;
e[tot].y=y;
e[tot].nxt=in[x];
in[x]=tot;
}
int size[maxn];
int DFs1(int v,int fa,int dep){
size[v]=1;
int deps=dep;
for(register int i=in[v];i;i=e[i].nxt){
int u=e[i].y;
if(u==fa)continue;
deps+=DFs1(u,v,dep+1);
size[v]+=size[u];
}
return deps;
}
int f[maxn];
void DFs2(int v,int fa){
for(register int i=in[v];i;i=e[i].nxt){
int u=e[i].y;
if(u==fa)continue;
f[u]=f[v]+(n-size[u])-size[u];
DFs2(u,v);
}
}
int main(){
std::cin>>n;
for(register int i=1,x,y;i<n;i++){
std::scanf("%d %d",&x,&y);
ins(x,y);
ins(y,x);
}
f[1]=DFs1(1,0,0);
DFs2(1,0);
int ans=0x3f3f3f3f,ansi=1;
for(register int i=1;i<=n;i++)
if(ans>f[i]){
ans=f[i];
ansi=i;
}
std::printf("%d %d\n",ansi,ans);
return 0;
}比较下求n次dep和的