「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;
}