「UR#5」怎样更有力气

解题思路

考虑没有限制的情况，一定是把操作离线下来，按照边权从小到达做。可以发现，如果没有限制，完全图是多余的，直接拿树边进行合并就可以了。我们要做这么一件事情，把每个点属于的图上联通块看做颜色，每次合并链上相邻两块颜色不一样的，那么我们再额外使用一个并查集，把树上相邻的颜色相同的点合并在一个集合里，每次跳到集合中最浅的点做图上的合并操作即可，复杂度 \(\mathcal O(n\alpha(n))\) 。
考虑一个操作的限制数量 \(cnt\) ，如果 \(cnt \geq\) 链上的点数，那么这些点仍然是联通的，所以可以直接当做没有限制的情况来做。于是发现，有限制的情况的链的点数不超过 \(p_i\) ，考虑暴力把这条链上的点拿出来。问题转化为有一个点集 \(S\) ，并且给出这个点集的补图，要合并联通块信息。涉及到补图可以试图用一个小技巧解决，拿出补图中度数最小的点 \(x\) ，有 \(\deg[x]\leq \min(|S|,\sqrt{p_i})\) 。划分成与 \(x\) 相连的点集和与 \(x\) 不相邻的点集两个问题考虑。所有不与 \(x\) 相连的点可以直接与 \(x\) 合并，所有与 \(x\) 相邻的点不超过 \(\sqrt{p_i}\) 个，可以直接枚举两个点合并。对于两个集合直接的连边，考虑与 \(x\) 相邻的集合的每一条对 \(x\) 不相邻集合的出边，如果出边数量 \(=\) 集合大小则无法连边，否则一定可以和 \(x\) 不相邻集合连边，直接连向 \(x\) 即可。总复杂度 \(\mathcal O(n \alpha(n))\) 。

code

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

    int ch = 0, f = 0; x = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

    if(f) x = -x;

}

const int N = 300005;

ll ans;

bitset<N> B, C;

vector<int> e[N];

vector<pair<int, int> > g[N];

int f[N][21], dep[N], ax[N], ay[N], aw[N], id[N], n, m, p, tot;

namespace Rose{

	vector<int> g[N];

	inline void dfs(int u, int fa){

		dep[u] = dep[fa] + 1, f[u][0] = fa;

		for(int i = 1; i <= 20; i++)

			f[u][i] = f[f[u][i-1]][i-1];

		for(auto v : g[u])

			if(v != fa) dfs(v, u);

	}

	inline int lca(int x, int y){

		if(dep[x] < dep[y]) swap(x, y);

		for(int i = 20; ~i; i--)

			if(dep[f[x][i]] >= dep[y]) x = f[x][i];

		if(x == y) return x;

		for(int i = 20; ~i; i--)

			if(f[x][i] != f[y][i])

				x = f[x][i], y = f[y][i];

		return f[x][0];

	}

}

struct Camlia{

	int fa[N];

	inline void init(){

		for(int i = 1; i <= n; i++) fa[i] = i;

	}

	inline int ask(int x){

		return x == fa[x] ? x : fa[x] = ask(fa[x]);

	}

	inline void merge(int x, int y, int z){

		int p = ask(x), q = ask(y);

		if(p == q) return;

		tot++, fa[p] = q, ans += z;

	}

}X1, X2;

inline bool cmp(int x, int y){ return aw[x] < aw[y]; }

int main(){

	read(n), read(m), read(p);

	for(int i = 2, x; i <= n; i++)

		read(x), Rose::g[x].push_back(i);

	for(int i = 1; i <= m; i++){

		id[i] = i;

		read(ax[i]), read(ay[i]), read(aw[i]);

	}

	for(int i = 1, x, y, z; i <= p; i++){

		read(x), read(y), read(z);

		g[x].push_back(make_pair(y, z));

	}

	sort(id + 1, id + m + 1, cmp);

	Rose::dfs(1, 0);

	X1.init(), X2.init();

	for(int i = 1; i <= m; i++){

		int x = id[i], u = ax[x], v = ay[x];

		int lca = Rose::lca(u, v);

		int dis = dep[u] + dep[v] - 2 * dep[lca] + 1;

		if((int) g[x].size() < dis - 1){

			u = X2.ask(u), v = X2.ask(v);

			while(u != v){

				if(dep[u] < dep[v]) swap(u, v);

				X1.merge(u, f[u][0], aw[x]);

				X2.fa[u] = X2.ask(f[u][0]), u = X2.ask(u);

			}

		}

		else{

			vector<int> A; A.push_back(lca);

			int now = u;

			while(now != lca)

				A.push_back(now), now = f[now][0];

			now = v;

			while(now != lca)

				A.push_back(now), now = f[now][0];

			for(auto ed : g[x]){

				e[ed.first].push_back(ed.second);

				e[ed.second].push_back(ed.first);

			}

			int mndeg = (int) A.size(), pos = 0;

			for(auto k : A)

				if((int) e[k].size() < mndeg)

					mndeg = (int) e[k].size(), pos = k;

			int size = (int) A.size() - (int) e[pos].size();

			for(auto k : e[pos]) B[k] = 1;

			for(auto k : A) if(!B[k]) X1.merge(pos, k, aw[x]);

			for(auto k1 : e[pos]){

				for(auto k2 : e[k1]) C[k2] = 1;

				for(auto k2 : e[pos])

					if(!C[k2]) X1.merge(k1, k2, aw[x]);

				for(auto k2 : e[k1]) C[k2] = 0;

			}

			for(auto k1 : e[pos]){

				int tmp = 0;

				for(auto k2 : e[k1]) if(!B[k2]) tmp++;

				if(tmp < size) X1.merge(k1, pos, aw[x]);

			}

			for(auto k : e[pos]) B[k] = 0;

			for(auto k : A) e[k].clear();

		}

	}

	cout << ans << endl;

	return 0;

}

巴特西

「UR#5」怎样更有力气

「UR#5」怎样更有力气

code

最新文章

热门文章