HDU 4118：Holiday's Accommodation 简单树形DP(2011 Asia ChengDu Regional Contest ) Holiday's Accommodation
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4118
题意：
有一棵树，树上每个节点都是一座房子，房子里有人，树的每条边都有一个权值（距离），所有人都要去别人家玩（通过最短路径），有两个要求：
①所有人都要去别人的房子（不能不动）
②不能同时有两个人去同一个房子
求这些人移动距离总和的最大值
题解：
如图所示的一棵树，可以发现最多可以经过AB条边6次，即B端点的三个点以及A端点的三个点都可以经过AB边，而BD边最多只能经过2次，分别为D点以及其他所有点中的某一个。
很明显树上每一条边都可以经过以该边为分界的两子树中较少的点数*2次（每当有一个方向的一个点通过该边就一定会有另一个方向的另一个点通过），进行一次简单的树形DP就可以得到答案了。
代码
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int N=1e5+1;
struct node
{
int to,cost;
node(int x=0,int y=0)
{
to=x,cost=y;
}
};
long long mmin(long long x,long long y)
{
return x<y?x:y;
}
long long mmax(long long x,long long y)
{
return x>y?x:y;
}
long long dp[N],res;
bool mark[N];
vector<node>q[N];
void Dfs(int id,long long value,int n)
{
mark[id]=true;
dp[id]=0;
for(int i=0;i<q[id].size();++i)
{
int v=q[id][i].to;
long long w=q[id][i].cost;
if(mark[v])continue;
Dfs(v,w,n);
dp[id]+=dp[v];
}
dp[id]++;
res+=mmin(dp[id],n-dp[id])*value*2;
}
void solve()
{
int T,a,b,n,Case=0;
long long c;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
q[i].clear();
res=0;
for(int i=1;i<n;++i)
{
scanf("%d%d%lld",&a,&b,&c);
q[a].push_back(node(b,c));
q[b].push_back(node(a,c));
}
memset(mark,0,sizeof(mark));
Dfs(1,0,n);
printf("Case #%d: %lld
",++Case,res);
}
}
int main()
{
solve();
return 0;
}