题目地址：洛谷：【P2173】[ZJOI2012]网络 – 洛谷、BZOJ：Problem 2816. — [ZJOI2012]网络

题目描述

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

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

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

1. 操作0：修改一个节点的权值。
2. 操作1：修改一条边的颜色。
3. 操作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表示操作类型。

1. k = 0为修改节点权值操作，之后两个正整数x和y，表示将节点x的权值vx修改为y。
2. k = 1为修改边的颜色操作，之后三个正整数u, v和w，表示将连接节点u和节点v的边的颜色修改为颜色w。满足0 ≤ w < C。
3. k = 2为查询操作，之后三个正整数c, u和v，表示查询所有可能在节点u到节点v之间的由颜色c构成的简单路径上的节点的权值的最大值。如果不存在u和v之间不存在由颜色c构成的路径，那么输出“-1”。

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

1. 对于修改节点权值操作，不需要输出信息。
2. 对于修改边的颜色操作，按以下几类输出：
   （输出满足条件的第一条信息即可，即若同时满足2和3，则只需要输出“Error 1.”。）
   1. 若不存在连接节点u和节点v的边，输出“No such edge.”。
   2. 若修改后不满足条件1，不修改边的颜色，并输出“Error 1.”。
   3. 若修改后不满足条件2，不修改边的颜色，并输出“Error 2.”。
   4. 其他情况，成功修改边的颜色，并输出“Success.”。
3. 对于查询操作，直接输出一个整数。

输入输出样例

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

说明

【数据规模】
对于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。

题解

乍一看，好像是图上问题，但是我们冷静分析一下，会发现以下语句。

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

这不就是维护一堆链嘛，用Splay就行啦。
我们建n*c个点，第i+p*c个点对应颜色p的i号点。
对于操作0，将所有x号点splay到根并且修改权值。
对于操作1，用个map<pair<int, int>, int>来存每条边目前是什么颜色，将原来的两个点一个splay到根，然后断开父子关系（split），然后将新点splay到根重新建立父子关系（merge），如果两个splay的根的儿子在同侧，则要翻转其中一个（有可能接上的时候v点在序列的最右端而非接口处）。
异常判断，不存在边即map里查不到，不满足条件1即splay到根后两个儿子都不为空，不满足条件2即两个节点同根。
对于操作2，由于我们知道常规的查询序列需要头尾各建一个空节点便于查询，但是这里一堆链操作好麻烦，我就改成了splay两个端点，从两个端点和子树最大值中取最大值，来代替空节点。先异常判断查一下是否同根，然后常规操作。
这个题调了2天，终于调出来了。第一个没看别人代码的splay2333。（但是你板子就是看别人代码写的哇）

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <map>
#include <stack>
#include <utility> 
typedef std::pair<int, int> PI;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline PI mpair(int first, int second) {
    return std::make_pair(first, second);
}

// variables

const int MAXN = 100005;

int n, m, c, k, op, ut, vt, wt, ct;
std::map<PI, int> edges;
int sta[MAXN], stop = 0;

// splay

struct Node {
    int val, mxv;
    bool rev;
    int ch[2], fa;
} tr[MAXN];

inline void update(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    tr[p].mxv = std::max(tr[p].val, std::max(tr[lch].mxv, tr[rch].mxv));
}

inline void pushdown(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[p].rev) {
        std::swap(tr[lch].ch[0], tr[lch].ch[1]);
        std::swap(tr[rch].ch[0], tr[rch].ch[1]);
        tr[lch].rev = !tr[lch].rev;
        tr[rch].rev = !tr[rch].rev;
        tr[p].rev = false;
    }
}

inline void pushto(int p) {
    while(tr[p].fa) {
        sta[stop++] = p;
        p = tr[p].fa;
    }
    while(stop > 0) {
        p = sta[--stop];
        pushdown(p);
    }
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool haslch(int p) {
    return tr[p].ch[0] != 0;
}

inline bool islch(int p, int q) {
    return tr[p].ch[0] == q;
}

inline void rotate(int p) { // p is child
    bool type = !isleft(p);
    int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[fa].ch[type] = tr[p].ch[!type];
    tr[p].ch[!type] = fa;
    tr[tr[fa].ch[type]].fa = fa;
    if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[p].fa = tr[fa].fa;
    tr[fa].fa = p;
    update(fa);
    update(p);
}

inline void splay(int p, int tar) {
    pushto(p);
    for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
        if(tr[tr[p].fa].fa != tar) {
            rotate(isleft(fa) == isleft(p) ? fa : p);
        }
    }
}

inline int findrt(int p) {
    while(tr[p].fa) p = tr[p].fa;
    return p;
}

inline void modifyv(int p, int val) {
    int pt;
    for(int i = 0; i < c; i++) {
        pt = p + i * n;
        splay(pt, 0);
        tr[pt].val = val;
        update(pt);
    }
}

inline void split(int p, int q) {
    splay(p, 0);
    splay(q, p);
    tr[p].ch[!isleft(q)] = 0;
    tr[q].fa = 0;
    update(p);
}

inline void merge(int p, int q) {
    splay(p, 0);
    splay(q, 0);
    if(haslch(p) == haslch(q)) {
        tr[q].rev = !tr[q].rev;
        std::swap(tr[q].ch[0], tr[q].ch[1]);
    }
    tr[p].ch[haslch(p)] = q;
    tr[q].fa = p;
    update(p);
}

inline void modifyc(int p, int q, int col) {
    PI pairt = mpair(p, q);
    if(!edges.count(pairt)) {
        printf("No such edge.\n");
        return;
    }
    int ocol = edges[pairt], pt = p + col * n, qt = q + col * n;
    if(ocol == col) {
        printf("Success.\n");
        return;
    }
    splay(pt, 0);
    splay(qt, 0);
    if((tr[pt].ch[0] && tr[pt].ch[1]) || (tr[qt].ch[0] && tr[qt].ch[1])) {
        printf("Error 1.\n");
        return;
    }
    if(findrt(pt) == findrt(qt)) {
        printf("Error 2.\n");
        return;
    }
    int pt1 = p + ocol * n, qt1 = q + ocol * n;
    split(pt1, qt1);
    merge(pt, qt);
    edges[pairt] = edges[mpair(q, p)] = col;
    printf("Success.\n");
}

inline int query(int p, int q) {
    if(p == q) return tr[p].val;
    if(findrt(p) != findrt(q)) {
        return -1;
    }
    splay(p, 0);
    splay(q, p);
    return std::max(std::max(tr[p].val, tr[q].val), tr[tr[q].ch[islch(p, q)]].mxv);
}

int main() {
    n = readint();
    m = readint();
    c = readint();
    k = readint();
    for(int i = 1; i <= n; i++) {
        tr[i].val = tr[i].mxv = readint();
        for(int j = 1; j < c; j++) {
            tr[i + j * n].val = tr[i + j * n].mxv = tr[i].val;
        }
    }
    for(int i = 1; i <= m; i++) {
        ut = readint();
        vt = readint();
        ct = readint();
        edges[mpair(ut, vt)] = ct;
        edges[mpair(vt, ut)] = ct;
        merge(ut + ct * n, vt + ct * n);
    }
    while(k--) {
        op = readint();
        if(op == 0) {
            ut = readint();
            wt = readint();
            modifyv(ut, wt);
        }
        if(op == 1) {
            ut = readint();
            vt = readint();
            wt = readint();
            modifyc(ut, vt, wt);
        }
        if(op == 2) {
            ct = readint();
            ut = readint();
            vt = readint();
            printf("%d\n", query(ut + ct * n, vt + ct * n));
        }
    }
    return 0;
}