Solution
$LCT$ 直接上$QuQ$
注意$cut$ 完 需要 $d[u + c * N]--$ 再 $link$, 不然会输出Error 1的哦
Code
1 #include2 #include 3 #include 4 #define rd read() 5 using namespace std; 6 7 const int N = 1e5 + 5; 8 9 int n, m, col, Q; 10 11 int read() { 12 int X = 0, p = 1; char c = getchar(); 13 for (; c > '9' || c < '0'; c = getchar()) 14 if (c == '-' ) p = -1; 15 for (; c >= '0' && c <= '9'; c = getchar()) 16 X = X * 10 + c - '0'; 17 return X * p; 18 } 19 20 void cmax(int &a, int b) { 21 if (a < b) 22 a = b; 23 } 24 25 namespace LCT { 26 int val[N], Max[N], f[N], ch[N][2], tun[N], d[N]; 27 #define lc(x) ch[x][0] 28 #define rc(x) ch[x][1] 29 int isroot(int x) { 30 return rc(f[x]) != x && lc(f[x]) != x; 31 } 32 33 int get(int x) { 34 return rc(f[x]) == x; 35 } 36 37 void up(int x) { 38 Max[x] = val[x]; 39 if (lc(x)) cmax(Max[x], Max[lc(x)]); 40 if (rc(x)) cmax(Max[x], Max[rc(x)]); 41 } 42 43 void rev(int x) { 44 swap(lc(x), rc(x)); 45 tun[x] ^= 1; 46 } 47 48 void pushdown(int x) { 49 if (tun[x]) { 50 if (lc(x)) rev(lc(x)); 51 if (rc(x)) rev(rc(x)); 52 tun[x] = 0; 53 } 54 } 55 56 void pd(int x) { 57 if (!isroot(x)) 58 pd(f[x]); 59 pushdown(x); 60 } 61 62 void rotate(int x) { 63 int old = f[x], oldf = f[old], son = ch[x][get(x) ^ 1]; 64 if (!isroot(old)) ch[oldf][get(old)] = x; 65 ch[x][get(x) ^ 1] = old; 66 ch[old][get(x)] = son; 67 f[old] = x; f[son] = old; f[x] = oldf; 68 up(old); up(x); 69 } 70 71 void splay(int x) { 72 pd(x); 73 for (; !isroot(x); rotate(x)) 74 if (!isroot(f[x])) 75 rotate(get(f[x]) == get(x) ? f[x] : x); 76 } 77 78 void access(int x) { 79 for (int y = 0; x; y = x, x = f[x]) 80 splay(x), ch[x][1] = y, up(x); 81 } 82 83 void mroot(int x) { 84 access(x); splay(x); rev(x); 85 } 86 87 int findr(int x) { 88 access(x); splay(x); 89 while (lc(x)) pushdown(x), x = lc(x); 90 return x; 91 } 92 93 void split(int x, int y) { 94 mroot(x); access(y); splay(y); 95 } 96 97 int link(int x, int y) { 98 if (d[x] > 1 || d[y] > 1) 99 return 1;100 mroot(x);101 if (findr(y) == x)102 return 2;103 f[x] = y;104 return 3;105 }106 107 int cut(int x, int y) {108 mroot(x);109 if (findr(y) != x || f[x] != y || ch[x][1])110 return 0;111 f[x] = ch[y][0] = 0;112 return 1;113 }114 }115 using namespace LCT;116 117 int main()118 {119 n = rd; m = rd; col = rd; Q = rd;120 for (int i = 1; i <= n; ++i) {121 int tmp = rd;122 for (int j = 0; j < col; ++j)123 val[i + j * n] = tmp;124 }125 for (int i = 1; i <= m; ++i) {126 int u = rd, v = rd, z = rd;127 link(u + z * n, v + z * n);128 d[u + z * n]++;129 d[v + z * n]++;130 }131 for (; Q; Q--) {132 int k = rd;133 if (k == 0) {134 int u = rd, v = rd;135 for (int j = 0; j < col; ++j) 136 mroot(u + j * n), val[u + j * n] = v, up(u + j * n);137 }138 if (k == 1) {139 int u = rd, v = rd, z = rd, flag = 0, c;140 for (int j = 0; j < col && !flag; ++j) {141 flag = cut(u + j * n, v + j * n);142 if (flag) c = j;143 }144 if (!flag) {puts("No such edge."); continue;}145 d[u + c * n]--; d[v + c * n]--;146 flag = link(u + z * n, v + z * n);147 if (flag == 1) {148 puts("Error 1.");149 link(u + c * n, v + c * n);150 d[u + c * n]++; d[v + c * n]++;151 }152 else if (flag == 2) {153 puts("Error 2.");154 link(u + c * n, v + c * n);155 d[u + c * n]++; d[v + c * n]++;156 }157 else {158 puts("Success.");159 d[u + z * n]++; d[v + z * n]++;160 }161 }162 if (k == 2) {163 int z = rd, u = rd, v = rd;164 u = u + z * n;165 v = v + z * n;166 mroot(u);167 if (findr(v) != u) {puts("-1"); continue;}168 printf("%d\n", max(Max[lc(v)], val[v]));169 }170 }171 }