題目鏈接

problem

給出一個無向圖，每條邊有一種顏色，每種顏色都構成一個森林，需要完成以下操作，

• 修改點權
• 修改邊的顏色
• 詢問某種顏色的森林中某條路徑上點權最大值

solution

顏色數量不超過10，所以對于每種顏色建一棵LCT，
修改點權，就對每種顏色的LCT都修改，
修改邊的顏色，就將原來顏色的LCT中這條邊斷掉，在新顏色的LCT中加上，這里需要判斷加入邊后是否還滿足是森林，所以需要統計每個點連出去的各種顏色點的數量，還要判斷是否會形成環，只要判斷原來兩點是否在同一棵樹中，
詢問操作則直接詢問即可，

code

/*
* @Author: wxyww
* @Date: 2020-02-26 07:36:20
* @Last Modified time: 2020-02-26 09:21:59
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
const int N = 10010;
ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

struct LCT {
	struct node {
		int ch[2],val,rev,mx,pre;
	}TR[N];
	int isroot(int cur) {
		return TR[TR[cur].pre].ch[0] != cur && TR[TR[cur].pre].ch[1] != cur;
	}
	int getwh(int cur) {
		return TR[TR[cur].pre].ch[1] == cur;
	}
	void up(int cur) {
		TR[cur].mx = max(TR[ls].mx,max(TR[rs].mx,TR[cur].val));
	}
	void pushdown(int cur) {
		if(TR[cur].rev) {
			TR[ls].rev ^= 1;TR[rs].rev ^= 1;
			swap(ls,rs);
			TR[cur].rev = 0;
		}
	}
void rotate(int cur) {
	int fa = TR[cur].pre,gr = TR[fa].pre,f = getwh(cur);

	if(!isroot(fa)) TR[gr].ch[getwh(fa)] = cur;
	TR[cur].pre = gr;
	if(TR[cur].ch[f ^ 1]) TR[TR[cur].ch[f ^ 1]].pre = fa;
	TR[fa].ch[f] = TR[cur].ch[f ^ 1];
	TR[fa].pre = cur;TR[cur].ch[f ^ 1] = fa;
	up(fa);up(cur);
}
	int sta[N],top;
	void splay(int cur) {
		sta[++top] = cur;

		for(int i = cur;!isroot(i);i = TR[i].pre) {
			// printf("%d\n",i);
			sta[++top] = TR[i].pre;
		}
		while(top) pushdown(sta[top--]);

		while(!isroot(cur)) {
			if(!isroot(TR[cur].pre)) {
				if(getwh(TR[cur].pre) == getwh(cur)) rotate(TR[cur].pre);
				else rotate(cur);
			}
			rotate(cur);
		}
	}

	void access(int cur) {
		for(int t = 0;cur;t = cur,cur = TR[cur].pre) {

			splay(cur);rs = t;up(cur);
		}
	}
	void makeroot(int cur) {
		access(cur);

		splay(cur);
		TR[cur].rev ^= 1;
	}
	void link(int x,int y) {
		// printf("%d\n",x);
		makeroot(x);TR[x].pre = y;
	}

	void cut(int x,int cur) {
		makeroot(x);access(cur);
		splay(cur);
		ls = TR[ls].pre = 0;
		up(cur);
	}

	void update(int cur,int c) {
		makeroot(cur);TR[cur].val = c;
		up(cur);
	}
	int find(int cur) {
		access(cur);splay(cur);
		while(ls) cur = ls;
		return cur;
	}
	int query(int x,int y) {
		if(find(x) != find(y)) return -1;
		makeroot(x);access(y);splay(y);
		return TR[y].mx;
	}
}t[10];


#define pi pair<int,int>
map<pi,int>ma;
int num[N][11];
int main() {
	// freopen("1.in","r",stdin);
	int n = read(),m = read(),C = read(),Q = read();
	for(int i = 1;i <= n;++i) {
		int x = read();
		for(int j = 0;j < C;++j) 
		t[j].TR[i].mx = t[j].TR[i].val = x;
	}
	for(int i = 1;i <= m;++i) {
		int u = read(),v = read(),w = read();
		ma[make_pair(u,v)] = ma[make_pair(v,u)] = w;
		num[u][w]++;num[v][w]++;

		t[w].link(u,v);
		// puts("!!!");
	}

	while(Q--) {
		int opt = read();
		if(opt == 0) {
			int x = read(),y = read();
			for(int j = 0;j < C;++j) {
				t[j].update(x,y);
			}
		}

		if(opt == 1) {
			int u = read(),v = read(),w = read();
			if(!ma.count(make_pair(u,v))) {
				puts("No such edge.");continue;
			}
			int tmp = ma[make_pair(u,v)];
			if(tmp == w) {puts("Success.");continue;}
			
			if(num[u][w] + 1 > 2 || num[v][w] + 1 > 2) {puts("Error 1.");continue;}

			// printf("%d %d\n",t[w].find(u),t[w].find(v));
			if(t[w].find(u) == t[w].find(v)) {
				puts("Error 2.");continue;}


			puts("Success.");

			t[tmp].cut(u,v);

			num[u][tmp]--;num[v][tmp]--;

			num[u][w]++;num[v][w]++;
			t[w].link(u,v);
			ma[make_pair(u,v)] = ma[make_pair(v,u)] = w;
		}


		if(opt == 2) {
			int c = read(),u = read(),v = read();
			printf("%d\n",t[c].query(v,u));
		}
	}


	return 0;
}

標籤：其他

上一篇：【HDU - 1029】Ignatius and the Princess IV （水題）

下一篇：【POJ - 2533】Longest Ordered Subsequence （最長上升子序列 簡單dp）