Description

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

1. 对于任意节点连出去的边中，相同颜色的边不超过两条。

2. 图中不存在同色的环，同色的环指相同颜色的边构成的环。

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

0. 修改一个节点的权值。

1. 修改一条边的颜色。

2. 查询由颜色c的边构成的图中，所有可能在节点u到节点v之间的简单路径上的节点的权值的最大值。

Input

　 　输入文件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表示操作类型。

0. k = 0为修改节点权值操作，之后两个正整数x和y，表示将节点x的权值vx修改为y。

1. k = 1为修改边的颜色操作，之后三个正整数u, v和w，表示将连接节点u和节点v的边的颜色修改为颜色w。满足0 ≤ w < C。

2. k = 2为查询操作，之后三个正整数c, u和v，表示查询所有可能在节点u到节点v之间的由颜色c构成的简单路径上的节点的权值的最大值。如果不存在u和v之间不存在由颜色c构成的路径，那么输出“-1”。

Output

　　 输出文件network.out包含若干行，每行输出一个对应的信息。

1. 对于修改节点权值操作，不需要输出信息。

2. 对于修改边的颜色操作，按以下几类输出：

　　　　a) 若不存在连接节点u和节点v的边，输出“No such edge.”。

　　　　b) 若修改后不满足条件1，不修改边的颜色，并输出“Error 1.”。

　　　　c) 若修改后不满足条件2，不修改边的颜色，并输出“Error 2.”。

　　　　d) 其他情况，成功修改边的颜色，并输出“Success.”。

　　  输出满足条件的第一条信息即可，即若同时满足b和c，则只需要输出“Error 1.”。

3. 对于查询操作，直接输出一个整数。

Sample Input

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

Sample Output

4

Success.

Error 2.

-1

Error 1.

5

Solution

一个非常裸的lct……

按颜色维护多颗lct即可

让题意坑了一次……如果改颜色的边之前就是当前颜色的话就Success

在此感谢夫哥向我伸出的援手

Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define N (100000+100) 8 using namespace std; 9 struct node 10 { 11 int x,y,c; 12 } E[N]; 13 int n,m,c,k,p=10000,x,y,z,opt,val; 14 int Father[N],Son[N][2],Val[N],Max[N],Rev[N],Ind[N]; 15 bool cmp(node a,node b){ return a.x
            
             y) swap(x,y); 95 E[i].x=x, E[i].y=y, E[i].c=z; 96 Link(x+z*p,y+z*p); 97 Ind[x+z*p]++; 98 Ind[y+z*p]++; 99 }100 sort(E+1,E+m+1,cmp);101 for (int i=1; i<=k; ++i)102 {103 opt=read();104 switch (opt)105 {106 case 0:107 {108 x=read(); val=read();109 for (int i=0; i
             
              y) swap(x,y);121 int id=getid(x,y);122 if (id && E[id].c==val)123 {124 printf("Success.\n");125 break;126 }127 if (id==0)128 {129 printf("No such edge.\n");130 break;131 }132 if (Ind[x+val*p]>=2 || Ind[y+val*p]>=2)133 {134 printf("Error 1.\n");135 break;136 }137 if (Find_root(x+val*p)==Find_root(y+val*p))138 {139 printf("Error 2.\n");140 break;141 }142 Cut(x+E[id].c*p,y+E[id].c*p);143 Ind[x+E[id].c*p]--;144 Ind[y+E[id].c*p]--;145 Link(x+val*p,y+val*p);146 Ind[x+val*p]++;147 Ind[y+val*p]++;148 E[id].c=val;149 printf("Success.\n");150 break;151 }152 case 2:153 {154 val=read(); x=read(); y=read();155 if (Find_root(x+val*p)!=Find_root(y+val*p))156 {157 printf("-1\n");158 break;159 }160 printf("%d\n",Query(x+val*p,y+val*p));161 break;162 }163 }164 }165 }