P8710

· · 题解

提供一种拓扑排序+并查集的解法。

简化题意：

给定两种操作：

  1. 将两个点纳入一个连通块。

  2. 将这个点所在的连通块的值 +t。

简述思路：

第一种操作自然让人想到并查集，重点看第二种操作。

我们想要对一整块序列都进行加和操作，回想我们之前学到过的数据结构，对于区间的操作下，可以通过维护懒标记来简化操作。

同理，我们大概也能把所需要加的值放在一个点上，等到必要的时候下放。

我们知道，并查集是一种树形结构，对于每一个并查集的合并，实际上是对根节点的嫁接，所以我们可以把懒标记先放在根节点上。

什么时候下放懒标记呢？最后结算答案的时候当然要下放。

那么中间操作的时候什么时候下放呢？我们可以思考合并的过程。前文已经提到，并查集的合并，是一个根节点接到另一个根节点上，那么新成为的那个根节点，下放标记的时候，显然不能传递到新增的那些节点上。所以我们要在合并之前，将即将成为新根节点的节点下放。

为了便于操作，我们直接把并查集的结构直接存成一个自根节点向下的有向图，然后，我们借助并查集将环结构略去，这样就成了一个 DAG。

发现这个性质之后，我们在最后直接拓扑排序下放懒标记即可。

//2023/9/23
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int fa[MAXN];
int find(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
struct linkstar{
    int from,to,next;
}edge[2*MAXN];
struct node{
    int mark,val;
    node(){mark=val=0;}
}point[MAXN];
int escnt,n,m;
int head[MAXN],du[MAXN];
void add(int from,int to)
{
    edge[++escnt].from=from;
    edge[escnt].to=to;
    edge[escnt].next=head[from];
    head[from]=escnt;
}
void pushdown(int x)//下放懒标记
{
    for (int i=head[x];i!=-1;i=edge[i].next){
        int y=edge[i].to;
        point[y].mark+=point[x].mark;
        point[y].val+=point[x].mark;
    }
    point[x].mark=0;
}
void toposort()//拓扑排序下放
{
    queue<int> que;
    for (int i=1;i<=n;i++){
        if(du[i]==0) que.push(i);
    }
    while(!que.empty()){
        int x=que.front();
        que.pop();
        for (int i=head[x];i!=-1;i=edge[i].next){
            int y=edge[i].to;
            du[y]--;
            point[y].mark+=point[x].mark;
            point[y].val+=point[x].mark;
            if(du[y]==0) que.push(y);
        }
        point[x].mark=0;
    }
}
int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    int opt,p,t;
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=m;i++){
        cin>>opt>>p>>t;
        if(opt==1){
            t=find(t),p=find(p);
            if(t==p) continue;//取消环的影响
            if(t<p) swap(t,p);
            fa[t]=p;
            du[t]++;
            pushdown(p);//下放新根节点的懒标记
            add(p,t);//直接建立树形结构，便于拓扑排序
        }
        if(opt==2){
            p=find(p);//维护当前块的懒标记
            point[p].mark+=t;
            point[p].val+=t;
        }
    }
    toposort();
    for (int i=1;i<=n;i++) cout<<point[i].val<<" ";
    return 0;
}