5 条题解

  • 1
    @ 2023-07-14 17:20:51
    #include <cctype>
    #include <cstdio>
    #include <cstring>
    #include <cassert>
    #include <algorithm>
    using namespace std;
    const int MAXSIZE=30000020;
    int bufpos;
    char buf[MAXSIZE];
    void init(){
        #ifdef LOCAL
            freopen("1985.txt","r",stdin);
        #endif
        buf[fread(buf,1,MAXSIZE,stdin)]='\0';
        bufpos=0;
    }
    int readint(){
        bool isneg;
        int val=0;
        for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
        bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
        for(;isdigit(buf[bufpos]);bufpos++)
            val=val*10+buf[bufpos]-'0';
        return isneg?-val:val;
    }
    char readchar(){
        for(;isspace(buf[bufpos]);bufpos++);
        return buf[bufpos++];
    }
    struct edge{
        int from,to,next;
    };
    struct graph{
        int n,m;
        edge e[400001];
        int first[100001];
        int fa[100001];
        int par[100001][21];
        int dep[100001];
        int dist[100001];
        int maxi;
        int sz[100001];
        int val[100001];
        void init(int n,int *a){
            this->n=n;
            maxi=32-__builtin_clz(n);
            m=0;
            memset(first,-1,sizeof(first));
            memcpy(val,a,sizeof(val));
            for(int i=1;i<=n;i++)
                fa[i]=i,sz[i]=1,dep[i]=1,dist[i]=val[i];
        }
        void addedge(int from,int to){
            e[++m]=(edge){from,to,first[from]};
            first[from]=m;
        }
        int getf(int x){
            return fa[x]==x?x:fa[x]=getf(fa[x]);
        }
        void dfs(int u,int pa){
            for(int i=1;i<=maxi;i++)
                par[u][i]=par[par[u][i-1]][i-1];
            for(int i=first[u];i!=-1;i=e[i].next){
                int v=e[i].to;
                if (v!=pa){
                    par[v][0]=u;
                    dep[v]=dep[u]+1;
                    dist[v]=dist[u]+val[v];
                    dfs(v,u);
                }
            }
        }
        int lca(int u,int v){
            if (dep[u]<dep[v])
                swap(u,v);
            int t=dep[u]-dep[v];
            for(int i=0;i<=maxi;i++){
                if (t&(1<<i))
                    u=par[u][i];
            }
            if (u==v)
                return u;
            for(int i=maxi;i>=0;i--){
                if (par[u][i]!=par[v][i])
                    u=par[u][i],v=par[v][i];
            }
            return par[u][0];
        }
        void link(int u,int v){
            int x=getf(u),y=getf(v);
            if (sz[x]>sz[y])
                swap(u,v),swap(x,y);
            fa[x]=y;
            sz[y]+=sz[x];
            sz[x]=0;
            addedge(u,v);
            addedge(v,u);
            par[u][0]=v;
            dep[u]=dep[v]+1;
            dist[u]=dist[v]+val[u];
            dfs(u,v);
        }
        int query(int u,int v){
            int lc=lca(u,v);
            return dist[u]+dist[v]-dist[lc]*2+val[lc];
        }
    }g;
    int a[100001];
    int main(){
        init();
        int n=readint();
        for(int i=1;i<=n;i++)
            a[i]=readint();
        g.init(n,a);
        for(int i=1;i<=n;i++){
            int u=readint(),v=readint();
            if (!u)
                continue;
            g.link(u,v);
        }
        int m=readint(),lastans=0;
        for(int i=1;i<=m;i++){
            char c=readchar();
            int u=readint()^lastans,v=readint()^lastans;
            if (c=='Q')
                printf("%d\n",lastans=g.query(u,v));
            else g.link(u,v);
        }
    }
    
    
  • 0
    @ 2017-02-23 16:32:10

    楼下你可能只是单纯的lct写挂了
    另感谢出题人放lct一条生路

    • @ 2017-02-24 14:56:38

      然而应该是评测机不够稳定导致的
      或者说不同的评测机差别有点大?
      同样的代码重交一遍就可以AC

  • 0
    @ 2017-02-06 08:39:38

    这道题居然卡LCT
    改成link时随机选一个点做父亲才AC
    求教如何卡LCT

  • 0
    @ 2016-04-06 13:53:54

    启发式合并+倍增LCA即可。每次合并时将所在的树大小小的(设为\(u\))合并到大的(设为\(v\)),将\(u\)的父亲设为\(v\),将\(u\)所在的整棵树以\(u\)为根重建。重建时维护倍增数组和\(dist\)数组(\(dist[u]\)表示\(u\)到\(u\)所在的树的根的距离)。查询时设\(LCA(u,v)=lc\),答案为
    \(dist[u]+dist[v]-2*dist[lc]+val[lc]\)(\(val[lc]\)表示\(lc\)的权值)。这样,每个点所在的树的大小在这个点被重建时至少会翻倍,
    因此每个点最多被重建 \(O(\log n)\) 次而每次重建一个点的复杂度为 \(O(\log n)\) 总共有n个点,因此最终的时间复杂度为
    \(O(n \log^2 n)\)

    C++ Code

    #include <cctype>
    #include <cstdio>
    #include <cstring>
    #include <cassert>
    #include <algorithm>
    using namespace std;
    const int MAXSIZE=30000020;
    int bufpos;
    char buf[MAXSIZE];
    void init(){
        #ifdef LOCAL
            freopen("1985.txt","r",stdin);
        #endif
        buf[fread(buf,1,MAXSIZE,stdin)]='\0';
        bufpos=0;
    }
    int readint(){
        bool isneg;
        int val=0;
        for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
        bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
        for(;isdigit(buf[bufpos]);bufpos++)
            val=val*10+buf[bufpos]-'0';
        return isneg?-val:val;
    }
    char readchar(){
        for(;isspace(buf[bufpos]);bufpos++);
        return buf[bufpos++];
    }
    struct edge{
        int from,to,next;
    };
    struct graph{
        int n,m;
        edge e[400001];
        int first[100001];
        int fa[100001];
        int par[100001][21];
        int dep[100001];
        int dist[100001];
        int maxi;
        int sz[100001];
        int val[100001];
        void init(int n,int *a){
            this->n=n;
            maxi=32-__builtin_clz(n);
            m=0;
            memset(first,-1,sizeof(first));
            memcpy(val,a,sizeof(val));
            for(int i=1;i<=n;i++)
                fa[i]=i,sz[i]=1,dep[i]=1,dist[i]=val[i];
        }
        void addedge(int from,int to){
            e[++m]=(edge){from,to,first[from]};
            first[from]=m;
        }
        int getf(int x){
            return fa[x]==x?x:fa[x]=getf(fa[x]);
        }
        void dfs(int u,int pa){
            for(int i=1;i<=maxi;i++)
                par[u][i]=par[par[u][i-1]][i-1];
            for(int i=first[u];i!=-1;i=e[i].next){
                int v=e[i].to;
                if (v!=pa){
                    par[v][0]=u;
                    dep[v]=dep[u]+1;
                    dist[v]=dist[u]+val[v];
                    dfs(v,u);
                }
            }
        }
        int lca(int u,int v){
            if (dep[u]<dep[v])
                swap(u,v);
            int t=dep[u]-dep[v];
            for(int i=0;i<=maxi;i++){
                if (t&(1<<i))
                    u=par[u][i];
            }
            if (u==v)
                return u;
            for(int i=maxi;i>=0;i--){
                if (par[u][i]!=par[v][i])
                    u=par[u][i],v=par[v][i];
            }
            return par[u][0];
        }
        void link(int u,int v){
            int x=getf(u),y=getf(v);
            if (sz[x]>sz[y])
                swap(u,v),swap(x,y);
            fa[x]=y;
            sz[y]+=sz[x];
            sz[x]=0;
            addedge(u,v);
            addedge(v,u);
            par[u][0]=v;
            dep[u]=dep[v]+1;
            dist[u]=dist[v]+val[u];
            dfs(u,v);
        }
        int query(int u,int v){
            int lc=lca(u,v);
            return dist[u]+dist[v]-dist[lc]*2+val[lc];
        }
    }g;
    int a[100001];
    int main(){
        init();
        int n=readint();
        for(int i=1;i<=n;i++)
            a[i]=readint();
        g.init(n,a);
        for(int i=1;i<=n;i++){
            int u=readint(),v=readint();
            if (!u)
                continue;
            g.link(u,v);
        }
        int m=readint(),lastans=0;
        for(int i=1;i<=m;i++){
            char c=readchar();
            int u=readint()^lastans,v=readint()^lastans;
            if (c=='Q')
                printf("%d\n",lastans=g.query(u,v));
            else g.link(u,v);
        }
    }
    
  • -1
    @ 2016-03-23 07:53:25

    沙发QWQ

  • 1

信息

ID
1985
难度
4
分类
小h的妹子树 点击显示
标签
(无)
递交数
89
已通过
40
通过率
45%
被复制
2
上传者