【UER #9】知识网络

bitset写错没调出来。。。

$O(n(n+m))$

暴力枚举起点，建立转移虚点，得到一个边权为$0/1$，点数$n+k$，边数为$O(n+m)$的图

然后广搜双端队列维护即可

$O(k(n+m)+\frac{n(n+m)} {w})$

考虑枚举颜色$k$，对于所有这种颜色的点，假设一开始$dis_u$均为$2$

并由此广搜预处理一个最短路图，复杂度为$O(k(n+m))$

由于图上有0边无0环，因此最短路图是拓扑图

那么选定其中一个点为起点，会将这个点的$dis\rightarrow dis-1$，其他同色点$dis$不变

同时，这个点在最短路图上的所有后记节点$dis\rightarrow dis-1$

那么对于最短路图上所有点，统计有多少个起点能够到达它，就能够知道以这种颜色点为起点时，这个点不同的$dis$出现次数

这是一个拓扑图$dp$问题，不好处理，因此考虑用$\text{bitset}$暴力存储所有能够转移的状态

由于需要维护的起点总数为$n$，单次只维护一个集合，因此无法直接用$\text{std::bitset}$

复杂度为$O(\frac{nm} {w})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=51000,INF=1e9+10;

int n,m,k;
struct Edge{
	int to,nxt,w;
} e[N*4];
int head[N],ecnt;
void AddEdge(int u,int v,int w=1){
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}

int Q[N*4],D[N*4],L,R,dis[N];
unsigned Ans[N];
vector <int> G[200];
int len;
struct BITSET{
	ull a[N/128];
	int count(){
		int c=0;
		rep(i,0,len) c+=__builtin_popcountll(a[i]);
		return c;
	}
	void set(int x){ a[x>>6]|=1ull<<x; }
	void clear(){ memset(a,0,(len+1)<<3); }
	void copy(const BITSET &t){ memcpy(a,t.a,(len+1)<<3); }
	void operator |= (const BITSET &t) { rep(i,0,len) a[i]|=t.a[i]; }
} BS[N];

int cnt,vis[N],ind[N];
void Topo(int sz){
	rep(i,1,n+k) ind[i]=0;
	rep(u,1,n+k) for(int i=head[u];i;i=e[i].nxt) if(dis[e[i].to]==dis[u]+e[i].w) ind[e[i].to]++;
	L=1,R=0;
	rep(i,1,n+k) if(dis[i]<1e6 && !ind[i]) Q[++R]=i;
	while(L<=R){
		int u=Q[L++];
		if(u<=n) {
			int t=BS[u].count();
			Ans[dis[u]]+=sz-t;
			Ans[dis[u]-1]+=t;
		}
		for(int i=head[u];i;i=e[i].nxt) if(dis[e[i].to]==dis[u]+e[i].w) {
			BS[e[i].to]|=BS[u];
			if(--ind[e[i].to]==0) Q[++R]=e[i].to;
		}
	}
}

void Bfs(int c){
	if(!G[c].size()) return;
	memset(dis,63,(n+k+2)<<2);
	L=2*(n+k),R=2*(n+k)-1;
	rep(i,0,G[c].size()-1) Q[++R]=G[c][i],D[R]=dis[G[c][i]]=2;
	while(L<=R){
		int u=Q[L++];

		for(reg int i=head[u];i;i=e[i].nxt){
			reg int v=e[i].to,w=e[i].w;
			if(dis[v]<=dis[u]+w) continue;
			dis[v]=dis[u]+w;
			if(!w) Q[--L]=v,D[L]=dis[v];
			else Q[++R]=v,D[R]=dis[v];
		}
	}
	len=G[c].size()/64;
	if(len>=N/128){
		len=N/128-1;
		rep(i,1,n+k) BS[i].clear();
		rep(i,0,G[c].size()-1) if(i<len*64) BS[G[c][i]].set(i);
		Topo(len*64);

		int tmp=len*64;
		len=(G[c].size()-tmp)/64;
		rep(i,1,n+k) BS[i].clear();
		rep(i,0,G[c].size()-1) if(i>=tmp) BS[G[c][i]].set(i-tmp);
		Topo(G[c].size()-tmp);
	} else {
		rep(i,1,n+k) BS[i].clear();
		rep(i,0,G[c].size()-1) BS[G[c][i]].set(i);
		Topo(G[c].size());
	}
}

int col[N];

int main(){
	n=rd(),m=rd(),k=rd();
	rep(i,1,n) {
		int x=col[i]=rd();
		AddEdge(n+x,i,0),AddEdge(i,n+x);
		G[x].pb(i);
	}
	rep(i,1,m) {
		int u=rd(),v=rd();
		if(col[u]==col[v]) continue;
		ind[u]++,ind[v]++;
		AddEdge(u,v),AddEdge(v,u);
	}
	rep(i,1,k) Bfs(i);
	Ans[1]=0;
	rep(i,2,k*2) Ans[i]/=2;
	Ans[k*2+1]=1ll*n*(n-1)/2;
	rep(i,1,k*2+1) printf("%u ",Ans[i]),Ans[k*2+1]-=Ans[i];
}