COJ983 WZJ的数据结构（负十七）

显然是动态树裸题：O(mlogn)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

inline int read()

{

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int sumv[maxn],val[maxn],pre[maxn],fa[maxn],ch[maxn][],flip[maxn];

void maintain(int x) {sumv[x]=sumv[ch[x][]]+sumv[ch[x][]]+val[x];}

void pushdown(int x)

{

    if(!flip[x]) return;

    flip[ch[x][]]^=;flip[ch[x][]]^=;

    swap(ch[x][],ch[x][]);flip[x]=;

}

void rotate(int x,int d)

{

    pushdown(x);int y=pre[x],z=pre[y];

    pre[ch[x][d]]=y;ch[y][d^]=ch[x][d];

    pre[x]=z;ch[z][ch[z][]==y]=x;

    pre[y]=x;ch[x][d]=y;maintain(y);

}

void splay(int x)

{

    int rt=x;while(pre[rt]) rt=pre[rt];

    if(rt!=x)

    {

        fa[x]=fa[rt];fa[rt]=;

        while(pre[x]) pushdown(pre[x]),rotate(x,ch[pre[x]][]==x);

        maintain(x);

    }

    else pushdown(x);

}

void access(int x)

{

    for(int y=;x;x=fa[x])

    {

        splay(x);pre[ch[x][]]=;fa[ch[x][]]=x;

        ch[x][]=y;pre[y]=x;fa[y]=;

        maintain(x);y=x;

    }

}

int findrt(int x)

{

    access(x);splay(x);

    while(ch[x][]) x=ch[x][];return x;

}

void makeroot(int x) {access(x);splay(x);flip[x]^=;}

void link(int x,int y) {makeroot(x);fa[x]=y;}

void query(int x,int y) {makeroot(x);access(y);splay(y);printf("%d\n",sumv[y]);}

int main()

{

    int n=read();

    for(int i=;i<=n;i++) val[i]=read();

    int m=read();

    while(m--)

    {

        char cmd=getchar();while(!isalpha(cmd)) cmd=getchar();

        int x=read(),y=read();

        if(cmd=='e')

        {

            if(findrt(x)==findrt(y)) query(x,y);

            else puts("impossible");

        }

        else

        {

            if(findrt(x)==findrt(y)) puts("no");

            else link(x,y),puts("yes");

        }

    }

    return ;

}

可以写个启发式合并O(mlog^2n)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

inline int read()

{

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

int first[maxn],next[maxn*],to[maxn*],e;

void AddEdge(int u,int v)

{

    to[++e]=v;next[e]=first[u];first[u]=e;

    to[++e]=u;next[e]=first[v];first[v]=e;

}

int val[maxn],pa[maxn],s[maxn];

inline int findset(int x) {return pa[x]==x?x:pa[x]=findset(pa[x]);}

int fa[maxn][],sum[maxn],dep[maxn];

void dfs(int x)

{

    sum[x]=sum[fa[x][]]+val[x];dep[x]=dep[fa[x][]]+;

    for(int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];

    for(int i=first[x];i;i=next[i]) if(to[i]!=fa[x][]) fa[to[i]][]=x,dfs(to[i]);

}

void query(int x,int y)

{

    int ret=sum[x]+sum[y],lca;

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=;i>=;i--) if((<<i)<=dep[x]-dep[y]) x=fa[x][i];

    for(int i=;i>=;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

    lca=(x==y)?x:fa[x][];

    printf("%d\n",ret-sum[lca]-sum[fa[lca][]]);

}

int main()

{

    int n=read();

    for(int i=;i<=n;i++) sum[i]=val[i]=read(),pa[i]=i,s[i]=;

    int m=read();

    while(m--)

    {

        char cmd=getchar();while(!isalpha(cmd)) cmd=getchar();

        int x=read(),y=read();

        if(cmd=='e')

        {

            int p1=findset(x),p2=findset(y);

            if(x==y) printf("%d\n",val[x]);

            else if(p1==p2) query(x,y);

            else puts("impossible");

        }

        else if(cmd=='b')

        {

            int p1=findset(x),p2=findset(y);

            if(p1==p2) {puts("no");continue;}puts("yes");

            if(s[p1]>s[p2]) swap(p1,p2),swap(x,y);

            pa[p1]=p2;s[p2]+=s[p1];fa[x][]=y;AddEdge(x,y);

            dfs(x);

        }

    }

    return ;

}