启发式合并 && U41492 树上数颜色

传送门

启发式合并

通俗点讲，就是将两个数据合并时，小的合并到大的里，这样就可以节约时间。

解题思路

再看看这个题，就是个板子题。

在两个节点信息合并起来时，让颜色数少的节点合并到颜色点多的节点上，实际操作时则是都是儿子的信息合并到父亲上，但是若儿子信息多于父亲，则交换一下信息（swap可做到O(1)）。

可以用map来操作，节约空间。　

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<vector>
11 #include<iomanip>
12 #include<ctime>
13 #include<stack>
14 using namespace std;
15 const int maxn=100005;
16 int n,m,cnt,p[maxn],a[maxn],ans[maxn];
17 map<int,int> mp[maxn]; 
18 struct node{
19     int v,next;
20 }e[maxn*2];
21 void insert(int u,int v){
22     cnt++;
23     e[cnt].v=v;
24     e[cnt].next=p[u];
25     p[u]=cnt;
26 }
27 void dfs(int u,int fa){
28     mp[u][a[u]]=1;
29     ans[u]=1;
30     for(int i=p[u];i!=-1;i=e[i].next){
31         int v=e[i].v;
32         if(v==fa) continue;
33         dfs(v,u);
34         if(ans[v]>ans[u]){//启发式合并
35             ans[u]=ans[v];
36             swap(mp[v],mp[u]);
37         }
38         for(map<int,int>::iterator it=mp[v].begin();it!=mp[v].end();it++){
39             if(mp[u][it->first]) continue;
40             else mp[u][it->first]=1,ans[u]++;
41         }
42     }
43 }
44 int main()
45 {
46     memset(p,-1,sizeof(p));
47     cin>>n;
48     for(int i=1;i<n;i++){
49         int u,v;
50         scanf("%d%d",&u,&v);
51         insert(u,v);
52         insert(v,u);
53     }
54     for(int i=1;i<=n;i++){
55         cin>>a[i];
56     }
57     dfs(1,-1);
58     cin>>m;
59     for(int i=1;i<=m;i++){
60         int x;
61         cin>>x;
62         cout<<ans[x]<<endl;
63     }
64     return 0;
65 }