BZOJ 4777 被权限了。
这道题的做法看上去不难，但是感觉自己yy不出来。
首先是两个结论：
1、答案一定是连接着两个异色点的一条边。
2、答案一定在最小生成树上。
感觉看到了之后都比较显然，自己想……算了吧……想不出来的……
那么我们可以对每一个点开一个以颜色为下标的线段树，对这棵树存一存它儿子的颜色到它的距离，然后在叶子结点维护一个$multiset$，把所有颜色相同的点都丢进去，然后维护一个最小值$lst_x = min(query(1, 1, k, 1, col_x - 1), query(1, 1, n, col_x + 1, k))$。
再全局维护一个$multiset$，每一次更改颜色的时候加入删除就好了。
时间复杂度$O(nlog^2n)$。
在Luogu上需要氧气。
Code：
#include#include #include #include using namespace std;typedef long long ll;const int N = 2e5 + 5;const int inf = 1 << 30;int n, m, k, qn, col[N], ufs[N], tot = 0, head[N];int lst[N], idCnt = 0, id[N * 40], fa[N], eVal[N];multiset ans, w[N * 40];struct Pathway { int u, v, val; friend bool operator < (const Pathway &x, const Pathway &y) { return x.val < y.val; } } pat[N];struct Edge { int to, nxt, val;} e[N << 1];inline void add(int from, int to, int val) { e[++tot].to = to; e[tot].val = val; e[tot].nxt = head[from]; head[from] = tot;}inline void addEdge(int x, int y, int v) { add(x, y, v), add(y, x, v);}inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}int find(int x) { return x == ufs[x] ? x : ufs[x] = find(ufs[x]);}inline void kruskal() { sort(pat + 1, pat + 1 + m); int cnt = 0; for(int i = 1; i <= n; i++) ufs[i] = i; for(int i = 1; i <= m; i++) { int u = find(pat[i].u), v = find(pat[i].v); if(u == v) continue; ufs[u] = v; addEdge(pat[i].u, pat[i].v, pat[i].val); ++cnt; if(cnt >= n - 1) break; }}inline int min(int x, int y) { return x > y ? y : x;}inline void chkMin(int &x, int y) { if(y < x) x = y;}namespace SegT { struct Node { int lc, rc, mn; } s[N * 40]; int root[N], nodeCnt = 0; #define lc(p) s[p].lc #define rc(p) s[p].rc #define mn(p) s[p].mn #define mid ((l + r) >> 1) inline void up(int p) { mn(p) = min(mn(lc(p)), mn(rc(p))); } void ins(int &p, int l, int r, int x, int v) { if(!p) mn(p = ++nodeCnt) = inf; if(l == r) { if(!id[p]) id[p] = ++idCnt; w[id[p]].insert(v); mn(p) = *(w[id[p]].begin()); return; } if(x <= mid) ins(lc(p), l, mid, x, v); else ins(rc(p), mid + 1, r, x, v); up(p); } void del(int &p, int l, int r, int x, int v) { if(l == r) { w[id[p]].erase(w[id[p]].find(v)); if(w[id[p]].empty()) mn(p) = inf; else mn(p) = *(w[id[p]].begin()); return; } if(x <= mid) del(lc(p), l, mid, x, v); else del(rc(p), mid + 1, r, x, v); up(p); } int query(int p, int l, int r, int x, int y) { if(!p) return inf; if(x <= l && y >= r) return mn(p); int res = inf; if(x <= mid) chkMin(res, query(lc(p), l, mid, x, y)); if(y > mid) chkMin(res, query(rc(p), mid + 1, r, x, y)); return res; } } using namespace SegT;inline int queryMin(int x) { int res = inf; if(col[x] != 1) chkMin(res, query(root[x], 1, k, 1, col[x] - 1)); if(col[x] != k) chkMin(res, query(root[x], 1, k, col[x] + 1, k)); return res;}void dfs(int x, int fat) { fa[x] = fat; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fat) continue; eVal[y] = e[i].val; ins(root[x], 1, k, col[y], e[i].val); dfs(y, x); } if(root[x]) { lst[x] = queryMin(x); ans.insert(lst[x]); }}int main() {// freopen("2.in", "r", stdin);// freopen("my.out", "w", stdout); read(n), read(m), read(k), read(qn); for(int i = 1; i <= m; i++) read(pat[i].u), read(pat[i].v), read(pat[i].val); kruskal(); for(int i = 1; i <= n; i++) read(col[i]); mn(0) = inf; dfs(1, 0); for(int x, v; qn--; ) { read(x), read(v); int pre = col[x]; col[x] = v; if(root[x]) { ans.erase(ans.find(lst[x])); lst[x] = queryMin(x); ans.insert(lst[x]); } if(fa[x]) { ans.erase(ans.find(lst[fa[x]])); del(root[fa[x]], 1, k, pre, eVal[x]); ins(root[fa[x]], 1, k, v, eVal[x]); lst[fa[x]] = queryMin(fa[x]); ans.insert(lst[fa[x]]); } printf("%d\n", *(ans.begin())); } return 0;}