P15391 最小生成树 / sosomst 题解

KobeBeanBryantCox · 2026-02-22 08:52:07 · 题解

P15391 最小生成树 / sosomst 题解

题目传送门。

题意

略。

思路

感觉不难（？

注意到前两个操作就是并查集，关键在于第三个操作。

考虑每个连通块维护一个动态开点线段树，维护 maxA,maxB,ans 三个信息，pushup 时有：

特别的，如果发现某个儿子是空的，代表这些全部都不是集合内的元素，此时直接求区间最大值给 maxB 即可，使用 st 表啥的弄一下都可以。

然后在并查集时写个线段树合并就好了，时间复杂度 O(n\log n)。

AC 代码

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=5e5+10;
int n,a[N],b[N],st[N][30];
int query(int l,int r)
{
    int k=__lg(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
struct Seg
{
    struct node{int lc,rc,maxa,maxb,ans;}tr[N*30];
    #define lc(x) tr[x].lc
    #define rc(x) tr[x].rc
    #define mid ((l+r)>>1)
    int cnt=0;
    void pushup(int x,int l,int r)
    {
        if(!lc(x))tr[lc(x)].maxb=query(l,mid);
        if(!rc(x))tr[rc(x)].maxb=query(mid+1,r);
        tr[x].ans=max({tr[lc(x)].ans,tr[rc(x)].ans,tr[lc(x)].maxa+tr[rc(x)].maxb});
        tr[x].maxa=max(tr[lc(x)].maxa,tr[rc(x)].maxa);
        tr[x].maxb=max(tr[lc(x)].maxb,tr[rc(x)].maxb);
    }
    void modify(int &x,int p,int l=1,int r=n)
    {
        if(!x)x=++cnt;
        if(l==r)return tr[x].maxa=a[p],tr[x].maxb=tr[x].ans=-1e9,void();
        if(p<=mid)modify(lc(x),p,l,mid);
        else modify(rc(x),p,mid+1,r);
        pushup(x,l,r);
    }
    int merge(int x,int y,int l=1,int r=n)
    {
        if(!x||!y)return x|y;
        lc(x)=merge(lc(x),lc(y),l,mid);
        rc(x)=merge(rc(x),rc(y),mid+1,r);
        pushup(x,l,r);return x;
    }
}T;
int rt[N],f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int merge(int u,int v)
{
    if((u=find(u))==(v=find(v)))return 114514;
    rt[u]=T.merge(rt[u],rt[v]),f[v]=u;
    return T.tr[rt[u]].ans;
}
void init()
{
    T.tr[0].ans=T.tr[0].maxa=-1e9;
    for(int i=1;i<=n;i++)st[i][0]=b[i];
    for(int j=1;j<=25;j++)for(int i=1;i+(1<<j)-1<=n;i++)
        st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)T.modify(rt[i],i);
}
int main()
{
//  freopen("sosomst.in","r",stdin),freopen("sosomst.out","w",stdout);
    in(),n=in();int t=in();
    for(int i=1;i<=n;i++)a[i]=in();
    for(int i=1;i<=n;i++)b[i]=in();
    init();int las=0;
    for(int i=1;i<n;i++)
    {
        int x=in()^(las*t),y=in()^(las*t);
        out(las=max(0,merge(x,y))),putchar('\n');
    }
    return 0;
}