染色

subtask 具有提示意义，考虑按 subtask 来分析。
1、只考虑每一列至多定下一种颜色，且首尾列都定下了
(dp_{i,c}) 表示做到第 (i) 个有颜色的列，该列另一个位置填 (c) 的方案数。
可以暴力转移，枚举上一列填了啥子，
这两列的关系有如下几种：

aa
bb

ab
ba

aa bc
bc aa

ab ca
ca ab

ab
cd

每一种颜色组合，中间的填色方案数，取决于 (i-j)，那么我们可以考虑手玩一个 dp 预处理这个系数。

复杂度 (O(nc^2)) 得分：0。

注意到对于每个颜色，本质不同的转移是 (O(1)) 的，用前缀和可以优化，这样一来复杂度可以做到 (O(nc))。得分：76。

考虑如果有一列有两种颜色怎么做：直接当成直接一种颜色，抹去另一行不合法颜色位置的值即可。得分：88。

考虑前后有一段空列怎么做：只跟空列数目有关，普及组dp预处理系数即可。得分：96。

参考代码（96分）

/*
g[i][0/1/2/3/4]

aa
bb

ab
ba

aa bc
bc aa

ab ca
ca ab

ab
cd
*/
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=100005,P=1e9+9;

inline int add(int a,int b){return (a+=b)>=P?a-P:a;}
inline int dec(int a,int b){return (a-=b)<0?a+P:a;}
inline int mul(int a,int b){static ll r;r=(ll)a*b;return r>=P?r%P:r;}

inline void Inc(int &a,int b){(a+=b)>=P&&(a-=P);}
inline void Dec(int &a,int b){(a-=b)<0&&(a+=P);}
inline void Mul(int &a,int b){a=mul(a,b);}

int n,c,f[N],g[N][5],a[N][2],dp[2][N],s[2],ans;

void init0()
{
	int G[5][5]={
		{0,1,0,2*(c-2),mul(c-2,c-3)},
		{1,0,2*(c-2),0,mul(c-2,c-3)},
		{0,1,c-2,c-3+c-2,add(mul(c-3,c-4),c-3)},
		{1,0,c-3+c-2,c-2,add(mul(c-3,c-4),c-3)},
		{1,1,2*(c-3),2*(c-3),add(mul(c-4,c-4),c-3)}
	}; // 各种状态间的转移系数
	g[1][1]=g[1][3]=g[1][4]=1;
	for(int i=2; i<=n; i++)
		for(int j=0; j<5; ++j)
			for(int k=0; k<5; ++k)
				Inc(g[i][j],mul(g[i-1][k],G[j][k]));
	f[0]=1; // 首尾空列的系数
	for(int i=1; i<=n; i++)
		f[i]=mul(f[i-1],add(mul(c-2,c-2),c-1));
}

struct node {
	int p,a,b;
}; vector<node> v;

void init1()
{
	// naive
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i][0]);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i][1]);
	for(int i=1; i<=n; i++)
		if(a[i][0]||a[i][1])
		{
			v.push_back((node){i,a[i][0],a[i][1]});
			if(a[i][0]==a[i][1])
			{
				puts("0");
				exit(0);
			}
		}
}

void work()
{
	int l=v.size();
	if(!l)
	{
		ans=mul(f[n-1],mul(c,c-1));
		return;
	}
	for(int k=1; k<=c; k++)
	{
		int a=v[0].a,b=v[0].b;
		if(a&&b&&(k!=b))
			continue;
		if(!a)a=k;
		if(!b)b=k;
		if(a==b)
			continue;
		dp[0][k]=f[v[0].p-1];
		Inc(s[0],dp[0][k]);
	}
	if(v[0].a==v[0].b)
		v[0].b=0;
	for(int i=1,cur=1; i<l; ++i,cur^=1)
	{
		s[cur]=0;
		for(int k=1; k<=c; k++)
		{
			dp[cur][k]=0;
			int ew=s[!cur];
			int a=v[i].a,b=v[i].b,c,p=v[i].p-v[i-1].p;
			if(a&&b&&(k!=b))
				continue;
			if(!a)a=k;
			if(!b)b=k;
			if(a==b)
				continue;
			if(v[i-1].a)
				c=v[i-1].a;
			else
				c=v[i-1].b,swap(a,b);
			if(a==c)
			{
				Inc(dp[cur][k],mul(dp[!cur][b],g[p][0]));
				Dec(ew,dp[!cur][b]);
				Inc(dp[cur][k],mul(ew,g[p][2]));
			}
			else if(b==c)
			{
				Inc(dp[cur][k],mul(dp[!cur][a],g[p][1]));
				Dec(ew,dp[!cur][a]);
				Inc(dp[cur][k],mul(ew,g[p][3]));
			}
			else
			{
				Inc(dp[cur][k],mul(dp[!cur][a],g[p][3]));
				Dec(ew,dp[!cur][a]);
				Inc(dp[cur][k],mul(dp[!cur][b],g[p][2]));
				Dec(ew,dp[!cur][b]);
				Inc(dp[cur][k],mul(ew,g[p][4]));
			}
			Inc(s[cur],dp[cur][k]);
		}
		if(v[i].a&&v[i].b)
			v[i].b=0;
		if(i==l-1)
			for(int k=1; k<=c; k++)
				Inc(ans,mul(dp[cur][k],f[n-v.back().p]));
	}
	
}

int main()
{
	scanf("%d%d",&n,&c);
	if(c>10000) return 0;
	init0();
	init1();
	work();
	printf("%d",ans);
	return 0;
}

dp 的过程和 PKUSC2019 d2t1 类似，可以直接写一个区间加乘线段树维护，时间复杂度 (O((n+c)logc))。得分：100。

世界地图

转化一下题意大概是这个：

有若干个 MST，各有 (O(n)) 个关键点。
要求支持把两个 MST 合并，保证只有关键点之间会添加 (O(n)) 条带权边，
要求能维护出 MST 的边权和，并且更新成一个新的大小 (O(n)) 的关键点集合（用于下一次合并）。
要求做到单次 (O(nlog n)) 左右的复杂度。

若关键点只有两个则只要考虑MST中 <u,v> 路径上最大的边即可（LCT 维护 MST 的思想）。
现在要维护任意两个关键点路径上的 max, 可以先在原 MST 上加上新边，再拉出新关键点的类似斯坦纳树状物。
我们考虑升序插入边，当一条边的两侧均有关键点时，他必定将成为某两个关键点之间路径上的 max，于是他被视为一条关键边。

struct MST {
	int n;
	vector<Edge> v;
	ll sum; // 非关键边的边权和
	ll getans()
	{
		ll t = sum;
		for(auto &e : v) t += e.w;
		return t;
	}
	void debug()
	{
		printf("n = %d
", n);
		for(auto &e : v)
			printf("<%d, %d> = %d
", e.u, e.v, e.w);
		printf("sum = %lld
", sum);
	}
}Pre[M], Suf[M], Mo;

void Merge(const MST& a, const MST& b, int *ew)
{
	int nn = a.n + b.n;
	ll sum = a.sum + b.sum;
	vector<Edge> v(a.v);
	for(auto &e : b.v)
		v.push_back(Edge(e.u + a.n, e.v + a.n, e.w));
	for(int j = 1; j <= n; j ++)
		v.push_back(Edge(a.n - n + j, a.n + j, ew[j]));
	sort(v.begin(), v.end(), [&](const Edge&a, const Edge&b) {
		return a.w < b.w;
	});
	// Points
	// [1, n] cup [nn - n + 1, nn]
	for(int i = 1; i <= nn; ++i) f[i] = i;
	Mo.v.clear();
	for(auto &e : v)
	{
		int u = find(e.u), v = find(e.v);
		if(u == v)
			continue;
		sum += e.w;
		int cu = u <= n || u > nn - n;
		int cv = v <= n || v > nn - n;
		if(cu && cv) {
			f[u] = v; sum -= e.w;
			if(u > nn - n) u = u - nn + n + n;
			if(v > nn - n) v = v - nn + n + n;
			Mo.v.push_back(Edge(u, v, e.w));
		}
		else if(cu)
			f[v] = u;
		else if(cv)
			f[u] = v;
		else
			f[u] = v;
	}
	Mo.n = n + n; Mo.sum = sum;
}

简单查询

恐怕这个题不太能做，博主水平有限请见谅。