Description：

给出一张图，每个点都有颜色，对每个点求出，如果把这个点从图中删去，那么会有多少对不连通的同色点对。

$1\leqslant n,m\leqslant 2\times10^5$

Solution：

首先建圆方树，然后对每种颜色的点建立虚树，然后一个直观的想法是考虑虚树上每个点删去后原图中有几个不连通的点对，但是这么想复杂度就不对了，正解是计算在原图中的每个点删掉后会使得这棵虚树上的哪几个点不连通，然后对于虚树上每条边的贡献就是两边大小乘积，在树上差分一下就行了。

一定要注意图不连通的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

int val[MAXN];

vector<int> col[1000001];

vector<int> t[MAXN];

namespace TREE

{

	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 dfn[MAXN],tot = 0;

	int dep[MAXN],top[MAXN],siz[MAXN],son[MAXN],fa[MAXN];

	int dis[MAXN];

	void dfs1(int k,int depth)

	{

		dfn[k] = ++tot;

		siz[k] = 1;dep[k] = depth;

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

		{

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

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

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

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

		}

		return;

	}

	void dfs2(int k,int tp)

	{

		top[k] = tp;

		if(son[k] == 0)return;

		dfs2(son[k],tp);

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

		{

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

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

		}

		return;

	}

	int LCA(int a,int b)

	{

		while(top[a] != top[b])

		{

			if(dep[top[a]] < dep[top[b]])swap(a,b);

			a = fa[top[a]];

		}

		return (dep[a] < dep[b] ? a : b);

	}

	int p[MAXN];

	bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

	int stack[MAXN],tp = 0;

	int sum[MAXN];

	long long diff[MAXN];

	int curcol;

	void dp(int k)

	{

		sum[k] = (val[k] == curcol);

		long long v = (val[k] == curcol),s = 0;

		for(vector<int>::iterator it = t[k].begin();it != t[k].end();++it)

		{

			dp(*it);

			if(dep[*it] != dep[k] + 1)

			{

				diff[fa[*it]] += 1ll * sum[*it] * (p[0] - sum[*it]);

				diff[k] -= 1ll * sum[*it] * (p[0] - sum[*it]);

			}

			sum[k] += sum[*it];

			s += v * sum[*it];

			v += sum[*it];

		}

		t[k].clear(); 

		s += v * (p[0] - sum[k]);

		diff[k] += s;diff[fa[k]] -= s;

		return;

	}

	void build()

	{

		tp = 0;

		sort(p + 1,p + 1 + p[0],cmp_dfn);

		stack[tp = 1] = p[1];

		for(int i = 2;i <= p[0];++i)

		{

			int lca = LCA(stack[tp],p[i]);

			if(lca == stack[tp])

			{

				stack[++tp] = p[i];

				continue;

			}

			while(tp >= 2)

			{

				if(dfn[lca] < dfn[stack[tp - 1]])

				{

					t[stack[tp - 1]].push_back(stack[tp]);

					--tp;

				}

				else

				{

					t[lca].push_back(stack[tp]);

					--tp;

					break;

				}

			}

			if(tp == 1 && dfn[lca] < dfn[stack[tp]])

			{

				t[lca].push_back(stack[tp]);

				stack[tp] = lca;

			}

			if(stack[tp] != lca)stack[++tp] = lca;

			stack[++tp] = p[i];

		}

		while(tp >= 2)t[stack[tp - 1]].push_back(stack[tp]),--tp;

		dp(stack[tp]);

		return;

	}

	long long ans[MAXN];

	bool vis[MAXN];

	void dfs(int k)

	{

		vis[k] = true;

		ans[k] = diff[k];

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

		{

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

			dfs(e[i].to);

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

		}

		return;

	}

}

namespace GRAPH

{

	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 cc = 0;

	int ins[MAXN];

	int dfn[MAXN],low[MAXN],tot = 0;

	int stack[MAXN],top = 0;

	void tarjan(int k)

	{

		col[val[k]].push_back(k);

		dfn[k] = low[k] = ++tot;

		stack[++top] = k;

		ins[k] = cc;

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

		{

			if(dfn[e[i].to] == 0)

			{

				tarjan(e[i].to);

				low[k] = min(low[k],low[e[i].to]);

				if(low[e[i].to] >= dfn[k])

				{

					int t;++n;

					do

					{

						t = stack[top--];

						TREE::add(t,n);

					}while(t != e[i].to);

					TREE::add(k,n);

				}

			}

			else

			{

				low[k] = min(low[k],dfn[e[i].to]);

			}

		}

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d",&val[i]);

	}

	int a,b;

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

	{

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

		GRAPH::add(a,b);

	}

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

	{

		if(val[i] != 0 && GRAPH::dfn[i] == 0)

		{

			++GRAPH::cc;

			GRAPH::tarjan(i);

		}

	}

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

	{

		if(TREE::dep[i] == 0)TREE::dfs1(i,i),TREE::dfs2(i,i);

	}

	long long sum = 0;

	for(int c = 1;c <= 1000000;++c)

	{

		TREE::p[0] = 0;

		int curtot = 0,thistot = 0;;

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

		{

			TREE::p[++TREE::p[0]] = col[c][i];++thistot;

			if(i == col[c].size() - 1 || GRAPH::ins[col[c][i + 1]] != GRAPH::ins[col[c][i]])

			{

				sum = sum + 1ll * curtot * thistot;

				curtot = curtot + thistot;

				thistot = 0;

				TREE::curcol = c;

				TREE::build();

				TREE::p[0] = 0;

			}

		}

	}

	for(int i = 1;i <= n;++i)if(!TREE::vis[i])TREE::dfs(i);

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

	{

		if(val[i] == 0)break;

		printf("%lld\n",TREE::ans[i] + sum);

	}

	return 0;

}