[ZJOI2012]网络

题目描述

有一个无向图G，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：

对于任意节点连出去的边中，相同颜色的边不超过两条。
图中不存在同色的环，同色的环指相同颜色的边构成的环。

在这个图上，你要支持以下三种操作：

修改一个节点的权值。
修改一条边的颜色。
查询由颜色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： 复制

输出样例#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。

题解：

思维难度比较低，细节很多，首先看到C<=10，果断开10棵LCT。

　　1.对于操作1，在每一个LCT中修改这个点的点权就好。

　　2.对于操作2，我的方法是用一个链表来存边，如果a和b之间没有边，就输出“No such edge”。用一个数组in来存出度，如果出度>2并且颜色改变，就输出“Error 2.”。然后判断一下这两个点是否联通，如果联通且不是直接联通，就输出“Error 2.”。其他情况直接link就好。

  1 //Never forget why you start
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<algorithm>
  8 #define ll(x) lct[x].child[0]
  9 #define rr(x) lct[x].child[1]
 10 #define son(x,t) lct[x].child[t]
 11 using namespace std;
 12 int n,m,C,k;
 13 int in[10005][10];
 14 struct Tree{
 15   struct LCT{
 16     int child[2],fa,size,x,mmax,rev;
 17     bool is_root;
 18   }lct[10005];
 19   void push_up(int x){
 20     lct[x].size=lct[ll(x)].size+lct[rr(x)].size+1;
 21     lct[x].mmax=max(lct[x].x,max(lct[ll(x)].mmax,lct[rr(x)].mmax));
 22   }
 23   void push_rev(int x){
 24     if(!x)return;
 25     swap(ll(x),rr(x));
 26     lct[x].rev^=1;
 27   }
 28   void push_down(int x){
 29     if(lct[x].rev){
 30       push_rev(ll(x));
 31       push_rev(rr(x));
 32       lct[x].rev^=1;
 33     }
 34   }
 35   void push(int x){
 36     if(!lct[x].is_root)push(lct[x].fa);
 37     push_down(x);
 38   }
 39   int getson(int x){
 40     return x==son(lct[x].fa,1);
 41   }
 42   void rotate(int x){
 43     if(lct[x].is_root)return;
 44     int fa=lct[x].fa,fafa=lct[fa].fa,t=getson(x);
 45     son(fa,t)=son(x,!t);if(son(x,!t))lct[son(x,!t)].fa=fa;
 46     lct[fa].fa=x;son(x,!t)=fa;
 47     lct[x].fa=fafa;
 48     if(!lct[fa].is_root)son(fafa,son(fafa,1)==fa)=x;
 49     else lct[x].is_root=1,lct[fa].is_root=0;
 50     push_up(fa);
 51     push_up(x);
 52   }
 53   void splay(int x){
 54     push(x);
 55     for(int fa;!lct[x].is_root;rotate(x))
 56       if(!lct[fa=lct[x].fa].is_root)
 57     rotate(getson(fa)==getson(x)?fa:x);
 58   }
 59   void access(int x){
 60     int y=0;
 61     do{
 62       splay(x);
 63       lct[rr(x)].is_root=1;
 64       lct[rr(x)=y].is_root=0;
 65       push_up(x);
 66       x=lct[y=x].fa;
 67     }while(x);
 68   }
 69   void mroot(int x){
 70     access(x);
 71     splay(x);
 72     push_rev(x);
 73   }
 74   void link(int u,int v){
 75     mroot(u);
 76     lct[u].fa=v;
 77   }
 78   void cut(int u,int v){
 79     mroot(u);
 80     access(v);splay(v);
 81     lct[ll(v)].fa=lct[v].fa;
 82     lct[ll(v)].is_root=1;
 83     ll(v)=lct[v].fa=0;
 84     push_up(v);
 85   }
 86   void change(int x,int y){
 87     mroot(x);
 88     lct[x].x=y;
 89     push_up(x);
 90   }//修改点
 91   bool judge(int x,int y){
 92     access(x);splay(x);while(ll(x))x=ll(x);
 93     access(y);splay(y);while(ll(y))y=ll(y);
 94     return x==y;
 95   }
 96   bool pd(int x,int y){
 97     mroot(x);
 98     access(y);splay(y);
 99     return (ll(y)==x)&&lct[ll(y)].size==1;
100   }
101   int query(int x,int y){
102     mroot(x);
103     access(y);splay(y);
104     return lct[y].mmax;
105   }
106 }T[10];
107 struct node{
108   int next,to,dis;
109 }edge[200005];
110 int head[10005],size=-1;
111 void putin(int from,int to,int dis){
112   size++;
113   edge[size].next=head[from];
114   edge[size].to=to;
115   edge[size].dis=dis;
116   head[from]=size;
117 }
118 int main(){
119   int i,j;
120   memset(head,-1,sizeof(head));
121   scanf("%d%d%d%d",&n,&m,&C,&k);
122   for(i=1;i<=n;i++){
123     int x;scanf("%d",&x);
124     for(j=0;j<C;j++){
125       T[j].lct[i].size=T[j].lct[i].is_root=1;
126       T[j].lct[i].x=T[j].lct[i].mmax=x;
127     }
128   }
129   for(i=1;i<=m;i++){
130     int u,v,c;
131     scanf("%d%d%d",&u,&v,&c);
132     putin(u,v,c);
133     putin(v,u,c);
134     in[u][c]++;
135     in[v][c]++;
136     T[c].link(u,v);
137   }
138   for(i=1;i<=k;i++){
139     int a,b,c,d;
140     scanf("%d%d%d",&d,&a,&b);
141     if(d==0){
142       
143       for(j=0;j<C;j++)
144     T[j].change(a,b);
145       
146     }
147     else if(d==1){
148       
149       scanf("%d",&c);
150       
151       bool flag=0;
152       for(j=head[a];j!=-1;j=edge[j].next)if(edge[j].to==b){flag=1;break;}
153       if(!flag){printf("No such edge.
");continue;}
154       
155       int last=edge[j].dis;
156       if((in[a][c]==2&&last!=c)||(in[b][c]==2&&last!=c)){printf("Error 1.
");continue;}
157 
158       if(T[c].judge(a,b)&&(!T[c].pd(a,b))){printf("Error 2.
");continue;}
159       
160       in[a][last]--;in[b][last]--;
161       in[a][c]++;in[b][c]++;
162       edge[j].dis=c;edge[j^1].dis=c;
163       T[last].cut(a,b);
164       T[c].link(a,b);
165       printf("Success.
");
166       
167     }
168     else if(d==2){
169       
170       scanf("%d",&c);
171       
172       if(!T[a].judge(b,c))printf("-1
");
173       else printf("%d
",T[a].query(b,c));
174       
175     }
176   }
177   return 0;
178 }