C++14(g++5.4) 解法, 执行用时: 381ms, 内存消耗: 63484K, 提交时间: 2019-06-08 14:36:45

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+10;
int ans[M],timing=0,n,m,co[M];
vector<int>v[M];
set<int>s[M];
void dfs(int x,int fa){
	for(int i=0;i<v[x].size();i++){
		int q=v[x][i];
		if(q==fa)continue;
		dfs(q,x);
		for(set<int>::iterator it=s[q].begin();it!=s[q].end();++it){
			s[x].insert(*it);
		}

	}
	s[x].insert(co[x]);
	ans[x]=s[x].size();
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&co[i]);
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,1);
	while(m--){
		int x;
		scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 394ms, 内存消耗: 63500K, 提交时间: 2023-03-20 01:25:33

#include<bits/stdc++.h>
using namespace std;

set<int>T[100005];
set<int>::iterator it;
vector<int>R[100005];
int ans[100005],V[100005];
void DFS(int x,int fa)
{
	int i,j;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j==fa)continue;
		DFS(j,x);
		for(it=T[j].begin();it!=T[j].end();it++)T[x].insert(*it);
	}
	T[x].insert(V[x]),ans[x]=T[x].size();
}
int main()
{
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&V[i]);
    for(i=0;i<n-1;i++)scanf("%d%d",&j,&k),R[j].push_back(k),R[k].push_back(j);
    DFS(1,0);
    while(m--)scanf("%d",&i),printf("%d\n",ans[i]);
    return 0;
}

C++(clang++11) 解法, 执行用时: 256ms, 内存消耗: 11828K, 提交时间: 2020-12-01 15:50:59

#include<set>
#include<vector>
#include<cstdio>
using namespace std;typedef set<int> S;int A[100010],C[100010],n,m,s,t,j;vector<int>G[100010];S d(int a,int v){S s,r;r.insert(C[a]);for(int i=0;i<G[a].size();i++){if(G[a][i]!=v){s=d(G[a][i],a);r.insert(s.begin(),s.end());}}A[a]=r.size();return r;}int main(){scanf("%d%d",&n,&m);for(j=1;j<=n;j++){scanf("%d",&C[j]);}for(j=0;j<n-1;j++){scanf("%d%d",&s,&t);G[s].push_back(t);G[t].push_back(s);}d(1,0);for(j=0;j<m;j++){scanf("%d",&t);printf("%d\n",A[t]);}return 0;}

pypy3 解法, 执行用时: 1198ms, 内存消耗: 72788K, 提交时间: 2023-03-30 16:53:16

n,m = map(int,input().split())
v = list(map(int,input().split()))
has = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    has[a].append(b)
    has[b].append(a)
ans = [1]*(n)
def dfs(x,p):
    xx = {v[x]}
    for y in has[x]:
        if y == p:continue
        yy = dfs(y,x)
        if len(xx) < len(yy):
            yy,xx = xx,yy
        xx.update(yy)
    ans[x] = len(xx)
    return xx
dfs(0,0)
for _ in range(m):
    print(ans[int(input())-1])