poj 1935(树形dp)

题目链接：http://poj.org/problem?id=1935

思路：首先我们考虑从源点出发到所有自己想要经过的点然后在回到源点sum，显然每条边都必须经过源点（这个我们可以一次dfs求出），但题目的意思是可以不用回到源点，那么我们可以再求源点到所有要经过的点的最远距离ans,于是答案便是sum-ans.

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 55555

 #define FILL(a,b) memset(a,b,sizeof(a))

 struct Edge{

     int v,w,next;

 }edge[MAXN<<];

 int n,m,k,NE;

 int head[MAXN];

 void Insert(int u,int v,int w)

 {

     edge[NE].v=v;

     edge[NE].w=w;

     edge[NE].next=head[u];

     head[u]=NE++;

 }

 int dist[MAXN],sum;

 bool vis[MAXN];

 void dfs(int u,int father)

 {

     for(int i=head[u];i!=-;i=edge[i].next){

         int v=edge[i].v,w=edge[i].w;

         if(v==father)continue;

         dist[v]=dist[u]+w;

         dfs(v,u);

         if(vis[v])sum+=*w,vis[u]=true;

     }

 }

 int main()

 {

     int u,v,w,ans;

     while(~scanf("%d%d",&n,&k)){

         NE=;

         FILL(head,-);

         for(int i=;i<n;i++){

             scanf("%d%d%d",&u,&v,&w);

             Insert(u,v,w);

             Insert(v,u,w);

         }

         scanf("%d",&m);

         FILL(vis,false);

         while(m--){

             scanf("%d",&u);

             vis[u]=true;

         }

         dist[k]=;

         sum=;

         dfs(k,-);

         ans=;

         for(int i=;i<=n;i++)if(vis[i]){

             ans=max(ans,dist[i]);

         }

         printf("%d\n",sum-ans);

     }

     return ;

 }