Description：

有一棵树，树的每个节点有颜色。定义 $s(i,j)$ 为 $i$ 到 $j$ 的颜色数量，求所有的 $\begin{align}sum[k]=\sum_{i=1}^ns(k,i)\end{align}$ 。

$1\leqslant n\leqslant 10^5$

Solution：

一个问题，点分治的本质是什么。

如果要把一个树进行分治，一个直接简单自然的想法是把根节点的每个子树划分成一个子问题，但是这样有的子问题太大，有的太小，在进行一些操作的时候复杂度会非常难看。

所以点分治就是优化这个划分子问题的过程，他把子问题划分的尽量均匀，从而保证了 $n\log n$ 的复杂度，并且划分的一个子问题还在一个联通块里。

所以说什么树上路径问题什么的都不重要，在做点分治的题的时候思维不能太局限。

观察这道题，有一个重要的性质，如果对于一个点 $i$ ，这个点的颜色在这个点到分治中心是第一次出现的，那么他和分治中心所有其他子树内的点都能产生一的贡献。

所以考虑每个颜色的贡献，那么假设我们现在分治到了 $k$ ，也就是说我们要统计所有经过 $k$ 的路径的贡献，那么我们把所有这些贡献按照 $i$ 到根的第一个颜色来分类（毕竟颜色是这个问题主要要处理的东西），那么我们就可以先一遍 $dfs$ 统计每个子树的大小，顺便统计一下每个答案的贡献记做 $color$ ，然后再进行第二遍 $dfs$ ，在进入某个点的时候抹掉这个点对答案的贡献，退出时计算贡献，这样到每个点的时候他到祖先的一条链还有它的子树都已经被清空了，就可以计算这个点的除了他到根这些颜色其他的颜色对这棵子树的贡献了，然而还有他到根的颜色，在统计一边即可，因为这些颜色会对除了这棵子树外的所有其他点产生贡献。

好像把这道题做复杂了，写了一些奇怪的东西，所以也就不再解释了，总之就是冷静分析一下各种情况并考虑根节点的特殊性。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int v[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int siz[MAXN],d[MAXN],s,root;

bool vis[MAXN];

#define INF 0x3f3f3f3f

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa && !vis[e[i].to])

		{

			getroot(e[i].to,k);

			siz[k] += siz[e[i].to];

			d[k] = max(d[k],siz[e[i].to]);

		}

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

long long ans[MAXN];

int col[MAXN],c[MAXN];

int cnt[MAXN];

int sum = 0,rem;

void calc_siz(int k,int fa)

{

	c[++c[0]] = v[k];

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		calc_siz(e[i].to,k);

		siz[k] += siz[e[i].to];

	}

	return;

}

void dfs1(int k,int fa)

{

	if(cnt[v[k]] == 0)

	{

		sum += siz[k];

		col[v[k]] += siz[k];

	}

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs1(e[i].to,k);

	}

	--cnt[v[k]];

	return;

}

void reset(int k,int fa)

{

	if(cnt[v[k]] == 0)

	{

		sum -= siz[k];

		col[v[k]] -= siz[k];

	}

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		reset(e[i].to,k);

	}

	--cnt[v[k]];

	return;

}

void set(int k,int fa)

{

	if(cnt[v[k]] == 0)

	{

		sum += siz[k];

		col[v[k]] += siz[k];

	}

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		set(e[i].to,k);

	}

	--cnt[v[k]];

	return;

}

void dfs2(int k,int fa,int num,int sum_)

{

	int col_ = col[v[k]];

	if(cnt[v[k]] == 0)++num;

	sum_ -= col[v[k]];col[v[k]] = 0;

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs2(e[i].to,k,num,sum_);

	}

	ans[k] += num * rem + sum_;

	--cnt[v[k]];

	col[v[k]] = col_;

	return;

}

int dfs3(int k,int fa,int tot)

{

	if(cnt[v[k]] == 0)++tot;

	int res = tot;

	ans[k] += tot;

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		res += dfs3(e[i].to,k,tot);

	}

	--cnt[v[k]];

	return res;

}

void dfs4(int k,int fa)

{

	siz[k] = 0;

	if(v[k] == v[root])return;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		dfs4(e[i].to,k);

		siz[k] += siz[e[i].to];

	}

	return;

}

void dfs5(int k,int fa)

{

	if(v[k] == v[root])return;

	ans[k] += rem;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs5(e[i].to,k);

	}

	return;

}

void calc(int k)

{

	int tot = 0;

	c[0] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		calc_siz(e[i].to,0);

		tot += siz[e[i].to];

	}

	sort(c + 1,c + 1 + c[0]);

	c[0] = unique(c + 1,c + 1 + c[0]) - c - 1;

	sum = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs1(e[i].to,0);

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		rem = tot - siz[e[i].to];

		reset(e[i].to,0);

		dfs2(e[i].to,0,0,sum);

		set(e[i].to,0);

	}

	sum = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		siz[e[i].to] = 0;

		dfs4(e[i].to,0);

		sum += siz[e[i].to];

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		rem = sum - siz[e[i].to];

		dfs5(e[i].to,0);

	}

	int ss = 0;

	++cnt[v[k]];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		ss += dfs3(e[i].to,0,1);

	}

	--cnt[v[k]];

	ans[k] += ss + 1;

	for(int i = 1;i <= c[0];++i)col[c[i]] = 0;

	return;

}

void divide(int k)

{

	vis[k] = true;

	calc(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		s = siz[e[i].to];root = 0;

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&v[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	s = n;root = 0;d[0] = INF;

	getroot(1,0);

	divide(root);

	for(int i = 1;i <= n;++i)printf("%lld\n",ans[i]);

	return 0;

}