树形动态规划 fjutoj-2131 第四集，聚集城市

第四集，聚集城市

TimeLimit:1000MS MemoryLimit:128MB

64-bit integer IO format: %lld

Problem Description

在小A解读完手机信息后,得到了特工们的位置情报以及他们最近将会又一次聚会（除了谈论了关于抓捕小A和小C的事情外,主要谈论了关于走私事情…）

因为小C原本是他们的内部人员，所以她知道这个组织有一个习惯，即特工们每次选择聚会的城市,他们都会选择使所有组员所在市距离聚会城市的路程的和最小的城市，而且每个城市最多有一名特工。

现在,小A知道了特工们的所在位置，小A根据城市地图绘制了一副简易图，图的如下信息:

1，有一副n个节点的双向无环图，每个节点表示一个城市。

2，每条边默认距离为1。

3，有m个城市里住了他们的组员。

根据这些信息，得出一个城市编号X（1<=X<=n），使X到这m个城市的距离的和最小。

小A知道这是他反击的机会,他需要证据,他不想在和小C一直过着颠簸流离的逃亡生活。他需要获取更多关于走私的信息,他才有足够多的证据端了这个组织.因此,他必须找到这个聚会城市、

Input

有多组测试案例

第一行输入两个正整数n和m。(2<n<=10000,1<m<=n）

第二行接下来输入m个正整数mi,表示城市mi有1名特工(mi!=mj,i!=j)、

接下来有n-1行，每一行输入两个正整数a和b,表示城市a和城市b相连、

Output

对于每组测试案例，输出符合的城市编号,如果有多个城市符合要求，则输出编号最小的那个城市、

SampleInput

SampleOutput

思路：先以1或任意节点为根节点深度优先搜索计算出根结点到所有需要到达点的距离，并且用数组cot[]记录各个点为根节点的子树有多少个含有所需要到达点的数量。

再次进行深搜更新dp[] 状态转移方程dp[to]=dp[now]+m-2*cot[to]

最后遍历一遍数组dp[]寻找最大值出现的位置即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 const int maxn = 10000+5;
 6 vector<int>e[maxn];
 7 int has[maxn],vis[maxn],minLen[maxn],cot[maxn],dp[maxn],n,m,num;
 8 //has:记录哪几个城市需要到达
 9 //vis:记录是否有搜索过
10 //minLen：记录1到所有需要到达城市的最小距离
11 //cot：记录儿子有多少个需要到达的城市
12 
13 //初始化
14 void init()
15 {
16     memset(vis,0,sizeof(vis));
17     memset(has,0,sizeof(has));
18     memset(cot,0,sizeof(cot));
19     memset(minLen,0,sizeof(minLen));
20     memset(dp,0,sizeof(dp));
21     for(int i= 1 ; i<=n; i++)
22         e[i].clear();
23 }
24 
25 //计算最短长度和每个点儿子有多少个需要到达的城市
26 int dfs1(int now,int dep)
27 {
28     int temp=0;
29     if(has[now])
30         temp=1;
31     minLen[now]=dep;
32     int len=e[now].size();
33     for(int i=0; i<len; i++)
34     {
35         int to =e[now][i];
36         if(!vis[to])
37         {
38             vis[to]=1;
39             temp=temp+dfs1(to,dep+1);
40         }
41     }
42     cot[now]=temp;
43     return temp;
44 }
45 
46 void dfs2(int now)
47 {
48     int len=e[now].size();
49     for(int i=0; i<len; i++)
50     {
51         int to = e[now][i];
52         if(!vis[to])
53         {
54             vis[to]=1;
55             dp[to]=dp[now]+m-2*cot[to];//状态转移方程
56             //dp[to] = dp[now] + m-cot[to](离父节点的所有城市+1)  -cot[to](离子节点的所有城市-1);
57             dfs2(to);
58         }
59     }
60 }
61 
62 int main()
63 {
64     while(~scanf("%d%d",&n,&m))
65     {
66         init();
67         for(int i = 0; i<m; i++)
68         {
69             scanf("%d",&num);
70             has[num]=1;
71         }
72         for(int i = 0 ; i <n-1; i++)
73         {
74             int x,y;
75             scanf("%d%d",&x,&y);
76             e[x].push_back(y);
77             e[y].push_back(x);
78         }
79         vis[1]=1;
80         dfs1(1,0);
81         for(int i=1; i<=n; i++)
82         {
83             if(has[i])
84                 dp[1]+=minLen[i];
85         }
86         memset(vis,0,sizeof(vis));
87         vis[1]=1;
88         dfs2(1);
89         int Min_dp=dp[1],lie=1;
90         for(int i=1; i<=n; i++)
91             if(dp[i]<Min_dp)
92             {
93                 Min_dp=dp[i];
94                 lie=i;
95             }
96         printf("%d\n",lie);
97     }
98     return 0;
99 }