自动搬运

查看原文

来自洛谷，原作者为

	消失的海岸线 **

搬运于2025-08-24 21:55:27，当前版本为作者最后更新于2018-01-12 21:56:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

丢个博客链接。。

这题打 LOJ 的 VP 的时候写暴力+卡常拿了 83分...

其实 YY 出做法是不困难的，考虑维护深度模 $K$ 意义下相同的节点，建 $K$ 颗树即可。

$k$ 较大的时候暴力跳，否则 $dfs$ 序+树状数组统计。

对于修改操作，用并查集将都是 $1$ 的串起来即可，开方 $log$ 次就变成 $1$ 了，和花神游历各国那题是一样的。

然后就没了...

结果巨不好写...

不要问我复杂度分析和块大小多大比较优...详细一点的可以看官方题解，贴个代码（逃

    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <iomanip>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define N 50010
    #define MX 500000
    #define ll long long
    using namespace std;
    #define fstc __attribute__((optimize("-O3")))
    #define IL __inline__ __attribute__((always_inline))
    char xB[1<<15],*xS=xB,*xT=xB;
    #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
    fstc IL ll read()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    #define OUT 2000000
    char Out[OUT],*ou=Out;
    int Outn[30],Outcnt;
    fstc IL void write(ll x)
    {
        if(!x)*ou++=48;
        else
        {
            for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
            while(Outcnt)*ou++=Outn[Outcnt--];
        }
    }
    #define K 20
    int n,Q;
    int path[N],path_top;
    ll a[N];
    int sqr[MX+10];
    struct graph
    {
        struct zgz
        {
            int next,to;
        }edge[N<<1];
        int head[N],cnt;
        fstc void init(){cnt=1;}
        fstc void add(int from,int to)
        {
            edge[cnt].to=to;
            edge[cnt].next=head[from];
            head[from]=cnt++;
        }
        fstc void ins(int from,int to)
        {add(from,to),add(to,from);}
    };
    struct Bit
    {
        int n;
        ll c[N<<1];
        fstc void add(int x,ll v)
        {
            for(;x<=n;x+=x&(-x))
            c[x]+=v;
        }
        fstc ll ask(int x)
        {
            ll ret=0;
            for(;x;x-=x&(-x))
            ret+=c[x];
            return ret;
        }
    };
    struct Unionset
    {
        int n;
        int fa[N];
        fstc void init(int x)
        {
            n=x;
            for(int i=1;i<=n;i++)fa[i]=i;
        }
        fstc int find(int x)
        {return fa[x]==x?x:fa[x]=find(fa[x]);}
        fstc void Union(int x,int y)
        {if(find(x)!=find(y))fa[fa[x]]=y;}
    };
    struct block
    {
        graph G;
        Unionset S;
        Bit B;
        int fa[N],deep[N];
        fstc void set_fa(int x,int f)
        {fa[x]=f,G.add(f,x);}
        int tim_in[N],tim_out[N],dfn;
        fstc void dfs(int x)
        {
            tim_in[x]=++dfn;
            B.add(dfn,a[x]);
            for(int i=G.head[x];i;i=G.edge[i].next)
            {
                int to=G.edge[i].to;
                deep[to]=deep[x]+1;
                dfs(to);
            }
            tim_out[x]=++dfn;
            B.add(dfn,-a[x]);
        }
        fstc void init()
        {
            S.init(n);
            for(int i=1;i<=n;i++)
            if(a[i]==1) S.Union(i,fa[i]);
            B.n=n<<1;
            for(int i=1;i<=n;i++)
            if(!fa[i])deep[i]=1,dfs(i);
        }
        fstc void modify(int x,ll v)
        {
            B.add(tim_in[x],v-a[x]),B.add(tim_out[x],a[x]-v);
            if(v==1)S.Union(x,fa[x]);
        }
        fstc void get_path(int x,int pos)
        {
            while(deep[x]>=deep[pos])
            {
                path[++path_top]=x;
                x=S.find(fa[x]);
            }
        }
        fstc ll ask(int x,int top)
        {return B.ask(tim_in[x])-B.ask(tim_in[fa[top]]);}
    }T[K+5];
    graph G;
    int fa[N],deep[N];
    int stk[N],top;
    int anc[N][17];
    fstc void dfs(int x)
    {
        stk[++top]=x;
        for(int i=1;i<=K&&i<top;i++)
        T[i].set_fa(x,stk[top-i]);
        for(int i=G.head[x];i;i=G.edge[i].next)
        {
            int to=G.edge[i].to;
            if(to==fa[x])continue ;
            fa[to]=x,deep[to]=deep[x]+1;
            dfs(to);
        }
        top--;
    }
    fstc void init()
    {
        for(int i=1;i<=K;i++)T[i].G.init();
        for(int i=1;i<=n-1;i++)
        {
            int x=read(),y=read();
            G.ins(x,y);
        }
        deep[1]=1;
        dfs(1);
        for(int i=1;i<=K;i++) T[i].init();
        for(int i=1;i<=n;i++) anc[i][0]=fa[i];
        for(int j=1;j<=16;j++)
        for(int i=1;i<=n;i++) anc[i][j]=anc[anc[i][j-1]][j-1];
    }
    fstc int jump(int x,int step)
    {
        for(int i=0;i<=16;i++)if((step&(1<<i))>0)x=anc[x][i];
        return x;
    }
    fstc void modify(int x)
    {
        if(a[x]==1) return ;
        ll pos;
        if(a[x]<=MX) pos=sqr[a[x]];
        else pos=sqrt(a[x]);
        for(int i=1;i<=K;i++)T[i].modify(x,pos);
        a[x]=pos;
    }
    fstc ll ask(int x,int pos,int step)
    {
        ll ret=0;
        while(deep[x]>deep[pos])
            ret+=a[x],x=jump(x,step);
        return ret;
    }
    fstc void get_path(int x,int pos,int step)
    {
        while(x!=pos)
        {
            if(a[x]>1)path[++path_top]=x;
            x=jump(x,step);
        }
        if(a[pos]>1)path[++path_top]=pos;
    }
    fstc int get_lca(int x,int y)
    {
        if(deep[x]<deep[y])swap(x,y);
        for(int i=16;i>=0;i--)
        if(deep[anc[x][i]]>=deep[y])x=anc[x][i];
        if(x==y)return x;
        for(int i=16;i>=0;i--)
        if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
        return anc[x][0];
    }
    fstc int main()
    {
        G.init();
        register int i,j;
        for(i=1;i<=MX;++i)
        sqr[i]=sqr[i-1]+((sqr[i-1]+1)*(sqr[i-1]+1)==i);
        n=read();
        for(i=1;i<=n;++i)a[i]=read();
        init();
        Q=read();
        while(Q--)
        {
            int opt=read(),s=read(),t=read(),k=read();
            int lca=get_lca(s,t),len=deep[s]+deep[t]-2*deep[lca];
            if(opt==0)
            {
                if(len%k!=0)modify(t),t=jump(t,len%k);
                if(deep[lca]%k==deep[s]%k)modify(lca);
                for(j=1;j<=2;++j)
                {
                    path_top=0;
                    swap(s,t);
                    int tmp=deep[s]-deep[lca]-1;
                    if(tmp<0)continue ;
                    int pos=jump(s,tmp/k*k);
                    if(k<=K) T[k].get_path(s,pos);
                    else get_path(s,pos,k);
                    for(int i=1;i<=path_top;i++)
                    modify(path[i]);
                }
            }
            else
            {
                ll ret=0;
                if(len%k>0)ret+=a[t],t=jump(t,len%k);
                if(deep[lca]%k==deep[s]%k)ret+=a[lca];
                if(k<=K)
                for(j=1;j<=2;++j)
                {
                    swap(s,t);
                    int tmp=deep[s]-deep[lca]-1;
                    if(tmp<0)continue ;
                    int pos=jump(s,tmp/k*k);
                    ret+=T[k].ask(s,pos);
                }
                else ret+=ask(s,lca,k),swap(s,t),ret+=ask(s,lca,k);
                write(ret),*ou++='\n';
            }
        }
        fwrite(Out,1,ou-Out,stdout);
        return 0;
}