题目
题目描述
有一个无向图G，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：
1.对于任意节点连出去的边中，相同颜色的边不超过两条。
2.图中不存在同色的环，同色的环指相同颜色的边构成的环。
在这个图上，你要支持以下三种操作：
0.修改一个节点的权值。
1.修改一条边的颜色。
2.查询由颜色c的边构成的图中，所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。
输入输出格式
输入格式：
输入文件network.in的第一行包含四个正整数N,M,C,K，其中N为节点个数，M为边数，C为边的颜色数，K为操作数。
接下来N行，每行一个正整数vi，为节点i的权值。
之后M行，每行三个正整数u,v,w，为一条连接节点u和节点v的边，颜色为w。满足1≤u,v≤N，0≤w<C，保证u≠v，且任意两个节点之间最多存在一条边(无论颜色)。
最后K行，每行表示一个操作。每行的第一个整数k表示操作类型。
k=0为修改节点权值操作，之后两个正整数x和y，表示将节点x的权值vx修改为y。
k=1为修改边的颜色操作，之后三个正整数u,v和w，表示将连接节点u和节点v的边的颜色修改为颜色w。满足0≤w<C。
k=2为查询操作，之后三个正整数c,u和v，表示查询所有可能在节点u到节点v之间的由颜色c构成的简单路径上的节点的权值的最大值。如果不存在u和v之间不存在由颜色c构成的路径，那么输出“-1”。
输出格式：
输出文件network.out包含若干行，每行输出一个对应的信息。
对于修改节点权值操作，不需要输出信息。
对于修改边的颜色操作，按以下几类输出：
a) 若不存在连接节点u和节点v的边，输出“No such edge.”。
b) 若修改后不满足条件1，不修改边的颜色，并输出“Error 1.”。
c) 若修改后不满足条件2，不修改边的颜色，并输出“Error 2.”。
d) 其他情况，成功修改边的颜色，并输出“Success.”。
输出满足条件的第一条信息即可，即若同时满足b和c，则只需要输出“Error 1.”。
对于查询操作，直接输出一个整数。
输入输出样例
输入样例#1：
4 5 2 7
1
2
3
4
1 2 0
1 3 1
2 3 0
2 4 1
3 4 0
2 0 1 4
1 1 2 1
1 4 3 1
2 0 1 4
1 2 3 1
0 2 5
2 1 1 4
输出样例#1：
4
Success.
Error 2.
-1
Error 1.
5
说明
颜色0为实线的边，颜色1为虚线的边，
由颜色0构成的从节点1到节点4的路径有1 – 2 – 4，故max{v1, v2, v4} = max{1,2,4}= 4。
将连接节点1和节点2的边修改为颜色1，修改成功，输出“Success.”
将连接节点4和节点3的边修改为颜色1，由于修改后会使得存在由颜色1构成的环( 1 – 2 – 4 – 3 – 1 )，不满足条件2，故不修改，并输出“Error 2”。
不存在颜色0构成的从节点1到节点4的边，输出“-1”。
将连接节点2和节点3的边修改为颜色1，由于修改后节点2的连出去的颜色为1的边有3条，故不满足条件1，故不修改，并输出“Error 1.”。
将节点2的权值修改为5。
由颜色1构成的从节点1到节点4的路径有 1 – 2 – 4，故max{v1, v2, v4} = max{ 1, 5, 4 } = 5。
【数据规模】
对于30%的数据：N ≤ 1000，M ≤ 10000，C ≤ 10，K ≤ 1000。
另有20%的数据：N ≤ 10000，M ≤ 100000，C = 1，K ≤ 100000。
对于100%的数据：N ≤ 10000，M ≤ 100000，C ≤ 10，K ≤ 100000。
题解
题目好长…
如果你做过这道题就会发现思路其实差不多
就是对每种颜色建$LCT$，先把点加入每个$LCT$中，边加入对应的$LCT$中
我们看看每个操作：
0.就是修改点权，枚举颜色修改就行了
1.还是枚举每种颜色的$LCT$，如果这个$LCT$中$x$和$y$相连
先$split(x,y)$一下
如果此颜色=修改颜色$dis$，就不用修改直接输出”Success.”
对于判断是否满足条件1，我们用一个数组$d$记录$x$连出去颜色$i$的边有几条，即$d_{x,i}$
这样随时更新$d$，如果$d_{x,dis}>1$或$d_{y,dis}>1$，就不满足，输出”Error 1.”
对于判断是否满足条件2，我们直接判断颜色编号为$dis$的$LCT$中$x$和$y$是否连通
如果连通，再加一条边肯定成同颜色环，就输出”Error 2.”
最后找不到就输出”No such edge.”
2.这个就是简单的输出了…如果在颜色编号为$dis$的$LCT$中不连通记得输出-1
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cstdlib>
using namespace std;
const int MAX=1e4+1;
int n,m,c,k;
int a[MAX];
int d[MAX][11];
struct Link_Cut_Tree{
int w[MAX],fa[MAX];
int son[MAX][2];
bool fl[MAX];
void pus(int x)
{
w[x]=max(max(w[son[x][0]],w[son[x][1]]),a[x]);
}
void down(int x)
{
if(fl[x]&&x)
{
if(son[x][1]) fl[son[x][1]]^=1;
if(son[x][0]) fl[son[x][0]]^=1;
swap(son[x][0],son[x][1]);
fl[x]=0;
}
}
bool is_root(int x)
{
return son[fa[x]][1]!=x&&son[fa[x]][0]!=x;
}
bool id(int x)
{
return son[fa[x]][0]==x?0:1;
}
void rot(int x)
{
int y=fa[x],z=fa[y],k=id(x);
if(!is_root(y)) son[z][id(y)]=x;
son[y][k]=son[x][k^1],fa[son[y][k]]=y;
son[x][k^1]=y,fa[y]=x;
fa[x]=z;
pus(y),pus(x);
}
void PUS(int x)
{
if(!is_root(x)) PUS(fa[x]);
down(x);
}
void splay(int x)
{
PUS(x);
for(int y;!is_root(x);rot(x))
if(!is_root(y=fa[x]))
rot(id(x)==id(y)?y:x);
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),son[x][1]=y,pus(x);
}
int find_root(int x)
{
access(x),splay(x);
while(son[x][0]) x=son[x][0];
return x;
}
void make_root(int x)
{
access(x),splay(x);
fl[x]^=1;
}
void split(int x,int y)
{
make_root(x),access(y),splay(y);
}
void cut(int x,int y)
{
split(x,y);
if(son[y][0]==x)
son[y][0]=0,fa[x]=0;
}
void link(int x,int y)
{
make_root(x);
fa[x]=y;
}
void change(int x,int dis)
{
access(x),splay(x);
a[x]=dis;
pus(x);
}
}Tree[11];
void CHANGE(int x,int y,int dis)
{
for(int i=1;i<=c;i++)
if(Tree[i].find_root(x)==Tree[i].find_root(y))
{
Tree[i].split(x,y);
if(Tree[i].son[y][0]!=x||Tree[i].son[x][1]) continue;
if(i==dis)
{
printf("Success.\n");
return;
}
if(d[x][dis]>1||d[y][dis]>1)
{
printf("Error 1.\n");
return;
}
if(Tree[dis].find_root(x)==Tree[dis].find_root(y))
{
printf("Error 2.\n");
return;
}
Tree[i].cut(x,y),Tree[dis].link(x,y);
d[x][i]--,d[y][i]--;
d[x][dis]++,d[y][dis]++;
printf("Success.\n");
return;
}
printf("No such edge.\n");
}
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
int main()
{
n=read(),m=read(),c=read(),k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
for(int j=1;j<=c;j++)
Tree[j].w[i]=a[i];
}
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),dis=read()+1;
d[x][dis]++,d[y][dis]++;
Tree[dis].link(x,y);
}
for(int i=1;i<=k;i++)
{
int op=read(),x,y,dis;
if(!op)
{
x=read(),y=read();
for(int j=1;j<=c;j++)
Tree[j].change(x,y);
}
else if(op==1)
{
x=read(),y=read(),dis=read()+1;
CHANGE(x,y,dis);
}
else if(op==2)
{
dis=read()+1,x=read(),y=read();
if(Tree[dis].find_root(x)!=Tree[dis].find_root(y))
printf("-1\n");
else
{
Tree[dis].split(x,y);
printf("%d\n",Tree[dis].w[y]);
}
}
}
return 0;
}
