题意简介
对于一个带权无向图，给出 \(Q\) 次操作，删除原图上边权小于 \(val\) 的边，查询某点所在连通块大小，在保证相对大小不变的情况下修改边权。
思路
考虑对原图建立最大生成树重构树，由于修改时不改变相对大小的特殊性，重构树的结构不会发生变化，故修改操作只需 \(O ( 1 )\) 修改此边对应点的点权。
由重构树的性质，深度较深的点权值更大，在查询操作时，只需树上倍增找到祖先节点中第一个边权 \(< val\) 的节点，那么删去这个点对应的边后，其子树内的所有点一定在一个连通块内，答案就是子树内叶子节点个数，单次查询复杂度 \(O ( n \log n )\)。
代码实现上有些小细节，比如本题并不保证原图连通，且操作三的修改必须保存到下一次操作一再执行，这是因为题中所说“原来已经断开的关系不会恢复”，若即时实现操作三会破坏上一次操作一的结果。
Code
#include<iostream>
#include<stack>
#include<utility>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=4e5+5;
const int LogN=20;
int n,m,Q,father[N<<1][LogN],dep[N<<1],son[N<<1][2],a[N<<1],siz[N<<1],pre,to[N];
stack<pair<int,int>>operat;
struct Node
{int u,v,w;Node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}bool operator<(const Node &tmp)const{return w>tmp.w;}
}edge[N];
struct Union_Find
{int leader[N<<1],point;void Init(int n){for(int i=1;i<=n;i++)leader[i]=i,siz[i]=1;}int Find(int k){if(leader[k]!=k) return leader[k]=Find(leader[k]);return k;}void Merge(int fu,int fv,int val){a[++point]=val;siz[point]=0;son[point][0]=fu;son[point][1]=fv;leader[fu]=point;leader[fv]=point;siz[point]+=siz[fu];siz[point]+=siz[fv];}
}DSU;
void Kruskal_Refactor()
{DSU.Init(n<<1);DSU.point=n;sort(edge+1,edge+m+1);for(int i=1;i<=m;i++){int fu=DSU.Find(edge[i].u);int fv=DSU.Find(edge[i].v);if(fu!=fv) DSU.Merge(fu,fv,edge[i].w),to[i]=DSU.point;}
}
void Dfs_pre(int u,int fa)
{if(!u) return;dep[u]=dep[fa]+1,father[u][0]=fa;for(int i=1;i<LogN;i++)father[u][i]=father[father[u][i-1]][i-1];Dfs_pre(son[u][0],u);Dfs_pre(son[u][1],u);
}
int Query(int pos,int k)
{for(int i=LogN-1;i>=0;i--)if(father[pos][i]&&a[father[pos][i]]>=k)pos=father[pos][i];return siz[pos];
}
int main()
{IOS;cin>>n>>m>>Q;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;edge[i]=(Node){u,v,w};}Kruskal_Refactor();for(int i=DSU.point;i>=1;i--)if(!dep[i]) Dfs_pre(i,0);while(Q--){int opt,x,val;cin>>opt;if(opt==1){cin>>x,pre=x;while(!operat.empty())a[to[operat.top().first]]=operat.top().second,operat.pop();}else if(opt==2)cin>>x,cout<<Query(x,pre)<<'\n';elsecin>>x>>val,operat.push({x,val});}return 0;
}
完结撒花～