某岛

… : "…アッカリ～ン . .. . " .. .
February 10, 2023

TypeDB Forces 2023

Problem G. Colorful Tree Again

题意：给定一个边权图，初始固定每个边有颜色和边权。每个节点也有颜色，初始都是黑色。
每次操作可以改变一个节点的颜色，并询问当前最大的好的路径的权值和是多少。
一个路径是好的，当且仅当路径上的所有点颜色相同，并包含了所有该颜色的边，且路径上经过的所有节点的颜色为白。

解法：这个题首先第一反应是 QTREE 4 和 QTREE 6 的某种结合。。。 但是仔细读题发现判定的条件是 path 而不是 component ！！！
因而题目难度大幅简化。。。但是想写得简洁依然会很困难。。。

首先第一步当然是剔除不合法的颜色。。。（最好用度数做简单的判定，不要在 dfs() 的时候判定。。）
然后再 dfs() 的时候，剩下的路径都有且仅有一个最高点。。我们对所有最高点位 u 的路径都放在一个堆里维护，记做 Q[u]…
那么在用所有的 Q[u] 组织一个堆来维护最优解。。（类似动态直径问题的点分树做法里最有的堆。。。）

那么每次 toggle 一个点时，除了会影响 Q[u].. 还会影响 u 向上的一条路径。。
记录那条路径所在的堆为 Q[y]，那么如果现在 Q[y] 包含在 ans 里时，更新 Q[y] 前后还要顺手更新一下 ans。
无论那种情况，我们现在都可以 O(1) 的 push()、pop() 操作进行处理。。

那么我们只需要实现一个可删除堆即可。。。stl 里的堆自然是不可定向删除的。。。
所以现在主流的 Dijkstra 模板里要求可删除堆的时候。。其实我们都是做延迟处理。。（尽管 clrs 里其实有可删除堆的相关代码。）

这里我们也可以用类似的方法。。。
对于每个堆，再开一个辅助堆，记录删除过的值即可。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e5) + 9;

struct heap {
	priority_queue<LL>Q, q;
	void push(LL x){if(x)Q.push(x);}
	void pop(LL x){if(x)q.push(x);}
	LL top() {
		while(!q.empty() && Q.top() == q.top()) Q.pop(), q.pop();
		if (Q.empty()) return 0;
		return Q.top();
	}
};

vector<pair<int, PII>> adj[N]; map<int, int> sub[N]; heap Q[N], ans;
LL W[N]; bool path[N], bad[N]; int top[N], upc[N], del[N];
 // 颜色的权值和，该颜色是否组成路径，节点是否已损坏，颜色的最高代表点，点到父亲的边的颜色，除最高点外路径被阻塞的次数
int n;



void dfs(int u = 1, int p = 0) {
    for (auto e: adj[u]) {
        int v = e.fi; if (v == p) continue;
        int w = e.se.fi, c = e.se.se;
        if (!top[c]) top[c] = u;
        upc[v] = c; dfs(v, u);
    }
}

void fix(int x) {
    if (bad[x]) {
        ans.pop(Q[x].top());
        if (x != 1) {
            int c = upc[x]; if (!path[c]) return;
            if (del[c]++) return;
            int y = top[c];
            if (!bad[y]) ans.pop(Q[y].top());
            Q[y].pop(W[c]);
            if (!bad[y]) ans.push(Q[y].top());
        }

    } else {
        ans.push(Q[x].top());
        if (x != 1) {
            int c = upc[x]; if (!path[c]) return;
            if (--del[c]) return;
            int y = top[c];
            if (!bad[y]) ans.pop(Q[y].top());
            Q[y].push(W[c]);
            if (!bad[y]) ans.push(Q[y].top());
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif
    int q; RD(n, q); DO(n-1) {
		int x, y, w, c; RD(x, y, w, c); ++sub[c][x]; ++sub[c][y]; W[c] += w;
		adj[x].PB({y, {w, c}}); adj[y].PB({x, {w, c}});
	}

	dfs();

    REP_1(c, n) if (W[c]) {
        int c1 = 0; path[c] = 1;
        for (auto e: sub[c]) {
            if (e.se == 1) ++c1;
            else if (e.se != 2) {
                path[c] = 0;
                break;
            }
        }
        path[c] &= c1 == 2;
        if (path[c]) Q[top[c]].push(W[c]);
    }

    REP_1(i, n) ans.push(Q[i].top());

    DO(q) {
	    int p, x; RD(p, x); bad[x] = !p; fix(x);
        printf("%lld\n", ans.top());
    }
}

Posted by xiaodao
Category: 日常

« | »

  • Archives

    open all | close all