编译

[Description]
山山是 2017 级信奥班的成员,因为喜欢玩 Android 系统而出名。
山山写出了一个伟大的 C++工程,一共包含 N 个源文件。在山山的脑海中,N 个源文
件构成一个树形结构。每一个源文件是树上的一个节点,其中 1 号节点是树根。
现在,山山开始编译这个工程。每次他会从树上选择一条链(包含两个端点)进行编译。
由于编译器的特性,要求这条链的一个端点必须是另一个端点的祖先。一条链可以退化成一
个点。每个源文件都需要被编译恰好一次。
每一个源文件都有一个两位十六进制数的标志值(范围从 00 到 ff)。对于每一条选择的
链,把该上面所有源文件的标志值异或起来,得到这条链的特征值。把所有选择的链的特征
值相加,得到这次编译的代价。现在山山想知道至少选择几条链才能编译所有文件。在选择
的链数目最小的时候,编译的代价最小是多少。
[Input]
第一行一个整数 N。
以下一行,N 个两位十六进制数,表示第 1 号源文件到第 N 号源文件的特征值。
(十六进制
数中的字母采取小写,不足两位的在前面补零。亦即 C/C++中使用”%02x”输出的格式。
)
以下(N - 1)行,每行两个整数,给出树上的一条边所连接的两个顶点。
[Output]
一行两个整数。依次为,选择的链的最小数目、编译的最小代价。两个数均以十进制形式输
出。
[Sample]

说明:最优方案为(1, 3), (2, 4), (5)或(1, 3), (2, 5), (4)。
[Tips]
0 ≤ N ≤ 20,000。

因为要求链的一个端点必须是另一个端点的祖先,因此可以论证,链的数量等于
叶子结点的数量;因此需要求的只有最小代价。
定义 dp[u][s] 为考虑子树 u ,并且点 u 所属的链当前的异或和为 s 时的最小代价。
由贪心法,每一个非叶子的点都必与一个子节点相连(否则链的数量无法达到最小),
因此对每一个点枚举与它相连的子节点即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long lol;
 7 struct Node
 8 {
 9   int next,to;
10 }edge[40001];
11 int num,head[20001];
12 lol f[20001][256],t[20001],cnt,cost[20001],n;
13 void add(int u,int v)
14 {
15   num++;
16   edge[num].next=head[u];
17   head[u]=num;
18   edge[num].to=v;
19 }
20 void dfs(int x,int pa)
21 {int flag=0,i,j;
22   lol sum=0;
23   for (i=head[x];i;i=edge[i].next)
24     {
25       int v=edge[i].to;
26       if (v!=pa)
27     {flag=1;
28       dfs(v,x);
29       sum+=t[v];
30     }
31     }
32   if (flag==0) 
33     {
34       ++cnt;
35       f[x][cost[x]]=cost[x];
36     }
37   for (i=head[x];i;i=edge[i].next)
38     {
39       int v=edge[i].to;
40       if (v!=pa)
41     {
42       for (j=0;j<=255;j++)
43         {
44           f[x][j^cost[x]]=min(f[x][j^cost[x]],sum-t[v]+f[v][j]+(j^cost[x])-j);
45         }
46     }
47     }
48   for (i=0;i<=255;i++)
49     t[x]=min(t[x],f[x][i]);
50 }
51 int main()
52 {int i,u,v;
53   cin>>n;
54   memset(f,127/2,sizeof(f));
55   memset(t,127/2,sizeof(t));
56   char ch=getchar();
57   for(i=1;i<=n;i++)
58   {
59     while(!(ch>='0'&&ch<='9'||ch>='a'&&ch<='f'))ch=getchar();
60     while(ch>='0'&&ch<='9'||ch>='a'&&ch<='f')
61     {
62       cost[i]=cost[i]*16;
63       if(ch<='9'&&ch>='0')cost[i]+=ch-'0';
64       else cost[i]+=ch-'a'+10;
65       ch=getchar();
66     }
67   }
68   for (i=1;i<=n-1;i++)
69     {
70       scanf("%d%d",&u,&v);
71       add(u,v);add(v,u);
72     }
73   dfs(1,0);
74   cout<<cnt<<' '<<t[1];
75 }