题目描述
blablabla
样例
blablabla
暴力只能过7/10;
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m;
int p[N];
//int w[N];
int h[N],e[2*N],ne[N+N],idx;
int find(int x)
{
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b)//合并
{
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
}
}
void add(int a,int b)//将可以接受到a点消息的所有点加上b
{
int pa=find(a);
for(int i=1;i<=n;i++)//找到和a节点在一个块的点
if(find(i)==pa)w[i]+=b;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
//memset(w,0,sizeof w);
for(int i=1;i<=n;i++)p[i]=i;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
if(a==1)
merge(b,c);
else add(b,c);
}
for(int i=1;i<=n;i++)
cout<<w[i]<<" ";
return 0;
}
并查集树上差分
大概思路是将所有在一个连通块里的节点加上相应的t值
但是如果就是一般的并查集的话,我们不能遍历集合里的每一个点
所以我们对于每一个合并操作,找到两个点所属的集合
如果这两个点不在同一连通块
那么我们构造一个新点,使这个新点成为集合合并后的根节点
这样进行 k次有效合并操作后,就会产生 k个新点
那我们所构造的图是若干棵树,编号为 1−n的节点都是树的叶子节点
然后我们对每次进行的2操作,将需要加的值保存在根节点里;
然后去遍历我们所有的n+1~k的根节点,将根节点保存的值遍历
下放到所有子节点当中即可;
最后输出1~n的权值
样例示意图
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m;
int p[N+M];
int w[N+M];
int h[N+M],e[2*M],ne[2*M],idx;
int find(int x)
{
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u)//遍历树的所有子节点
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
w[j]+=w[u];
dfs(j);
//cout<<e[i]<<endl;
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
//memset(w,0,sizeof w);
for(int i=1;i<=n+m;i++)p[i]=i;
int k=n+1;
while(m--)
{
int op,a,b;
cin>>op>>a>>b;
if(op==1)
{
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=k,p[pb]=k;//连到新节点上
add(k,pa),add(k,pb);//加边
k++;
}
}
else
{
int pa=find(a);
w[pa]+=b;//将值保存在根上
}
}
for(int i=n+1;i<k;i++)
if(p[i]==i)dfs(i);//下放根中的值
for(int i=1;i<=n;i++)
cout<<w[i]<<" ";
return 0;
}