传智杯3初赛(森林)
作者:
ericf
,
2022-11-16 19:40:02
,
所有人可见
,
阅读 322
这个题看了好久,最后偷点别人的代码终于Accepted 真tm长 歪日它day
倒序并查集
#include<iostream>//总结,操作二是这三个中比较难理清的,只需开个数组来存每次操作的前一个值
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5+10;
int n,m;
bool link[N];//判断这个边是否存在
int f[N],sum[N];//f数组判断此节点的father,sum记录所有父节点的和
struct point{
int a,b;//存边的编号对应的两个点
} nums[N];
struct node{//主要是对于操作二
int op;
int u;
int v;
}options[N]; //操作的类型和操作的哪一个边;
vector<int>res;//记录查询的结果
int last[N],val[N];//每个节点的老状态和新状态记录下来
//下面俩是并查集模板
int find(int x) {
return (x==f[x])?x:f[x]=find(f[x]);
}
void merge(int x,int y) {
int a=find(x);
int b=find(y);
if(a!=b) {
f[a]=b;
sum[b]+=sum[a];
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>sum[i]; //每个节点的灵值
}
for(int i=1; i<n; i++) { //对应第十行
cin>>nums[i].a>>nums[i].b;
}
for(int i=1; i<=m; i++) {
int op;
cin>>op;
options[i].op=op;
if(op==1) {
int u;
cin>>u;
options[i].u=u;
link[u]=true;
} else if(op==2) {
int u,v;
cin>>u>>v;
options[i].u=u;
options[i].v=v;
last[i]=sum[u];
sum[u]=v;
} else {
cin>>options[i].u;
}
}
for(int i=1; i<=n; i++) {
f[i]=i;
}
for(int i=1; i<n; i++) {
if(link[i]==false) {
merge(nums[i].a,nums[i].b);
}
}
for(int i=m; i>=1; i--) {
if(options[i].op==1) {
int u=options[i].u;
merge(nums[u].a,nums[u].b);
} else if(options[i].op==2) {
int u=options[i].u;
int v=options[i].v;
int ff=find(u);
sum[ff]-=v;
sum[ff]+=last[i];
}
else{
int u=find(options[i].u);
res.push_back(sum[u]);
}
}
reverse(res.begin(),res.end());
for(int i=0;i<res.size();i++)
{
cout<<res[i]<<endl;
}
return 0;
}