突然发现深究一些树上问题还是挺有意思的哈。
显然对于同一种权值的任意两个结点，其两端的部分都是不合法的。
维护两个标记表示子树内均不合法和子树外均不合法即可。但相同权值对数是 (Oleft(n^2 ight)) 的，我们要优化这个过程。
发现很多对都是无用的。DFS 下去，遇到一个 (x) 权值的结点 (u)，其实只需要与上一个遇到的 (x) 权值的结点 (v) 做一下就好了，原因如下：
- (v) 是 (u) 的祖先。(u) 与 (v) 子树外的结点做没有影响。
- (v) 不是 (u) 的祖先。能不经过其它 (x) 权值的除 (v) 外的结点直接走到 (u) 的 (x) 权值的结点一定已经做过了且 (u) 与它们做没有影响。
红色结点表示权值 (x) 的结点，蓝色结点就是 (u)。
画图就会发现这个结论太容易得出啦。
最后再来一次 DFS 处理所有标记。记一下是否存在子树外均不合法标记和当前子树内合法结点数。当一个结点的两个儿子中都出现子树外均不合法时答案一定为 (0)。细节仔细思考一下。
时间复杂度 (Oleft(nlog n ight))。瓶颈在于离散化，放一下代码叭。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define For(i,x,y)for(i=x;i<=(y);i++)
struct node
{
int next,to;
}e[400005];
map<int,int>col;
bool vis[N],fa[N],son[N];
int a[N],head[N],sta[N],last[N],pos[N],g,cnt,top;
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
inline void add(int u,int v)
{
e[++g].to=v;
e[g].next=head[u];
head[u]=g;
}
void dfs(int u,int t)
{
int i,v,tmp;
vis[u]=1;
sta[++top]=u;
pos[u]=top;
if(!col.count(a[u]))tmp=col[a[u]]=++cnt;
else
{
tmp=col[a[u]];
if(vis[last[tmp]])fa[sta[pos[last[tmp]]+1]]=1;
else son[last[tmp]]=1;
son[u]=1;
}
last[tmp]=u;
for(i=head[u];i;i=e[i].next)
{
v=e[i].to;
if(v==t)continue;
dfs(v,u);
last[tmp]=u;
}
vis[u]=0;
top--;
}
pair<int,int>calc(int u,int t)
{
int i,v,tot,siz;
pair<int,bool>pa;
tot=siz=0;
for(i=head[u];i;i=e[i].next)
{
v=e[i].to;
if(v==t)continue;
pa=calc(v,u);
/*cout<<v<<' '<<pa.first<<' '<<pa.second<<endl;*/
siz+=pa.second;
if(siz>1)cout<<0,exit(0);
if(!siz)tot+=pa.first;
else if(pa.second)tot=pa.first;
}
return make_pair((son[u]?0:tot+(!siz)),siz||fa[u]);
}
int main()
{
int n,i,u,v;
n=read();
For(i,1,n)a[i]=read();
For(i,1,n-1)
{
u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,0);
/*For(i,1,n)cout<<son[i]<<' '<<fa[i]<<endl;*/
cout<<calc(1,0).first;
return 0;
}