2021-10-22 C++洛谷超水（滑稽）题：hello world（提升版）

有一次一个朋友给我发了一道题，我看了后笑了。

 这么简单的题，我简简单单的回了一句：cout<<"Hello,World!";

过了一会朋友说不是这道题，随后把链接发给了我，我打开看了后才发现  

“一切并非这么简单”

那道题竟是这样的：你们可以看看，链接：Hello world! - 洛谷

呃呃呃呃呃呃呃呃~~~~~

朋友发到：你帮帮我吧！

我：你不做不行吗？？？

朋友：嘿，你不会了是吧，你个zz；

我：已急；

我一会胳膊，开干！

此题的代码：     拒绝复制！！！！！！

#include 
using namespace std;
typedef long long ll;
const int N = 50005, M = (N << 1), K = 255;
ll rd() {
	char c = getchar(); ll x = 0ll, f = 1ll;
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return x * f;
}
int n, m, q, ecnt = 0, fir[N], to[M], nxt[M], fa[N][16], nx[N][K], depth[N], f[N];
ll a[N];
#define fa(x) fa[x][0]
void ae(int u, int v) {to[++ecnt] = v; nxt[ecnt] = fir[u]; fir[u] = ecnt;}
void dfs(int u, int f) {
	int i; nx[u][0] = u, fa[u][0] = nx[u][1] = f, depth[u] = depth[f] + 1;
	for (i = 1; i <= 15; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (i = 2; i <= m; ++i) nx[u][i] = nx[f][i - 1];
	for (i = fir[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v != f) dfs(v, u);
	}
}
int up(int x, int k) {
	int i; if (k <= m) return nx[x][k];
	for (i = 15; ~i; --i) if (k >= (1 << i)) x = fa[x][i], k -= 1 << i;
	return x;
}
int lca(int u, int v) {
	int i; if (depth[u] < depth[v]) swap(u, v);
	for (i = 15; ~i; --i) if (depth[fa[u][i]] >= depth[v]) u = fa[u][i];
	if (u == v) return u;
	for (i = 15; ~i; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
int find(int u) {return f[u] = f[u] == u ? u : find(f[u]);}
void upd(int x) {
	if (a[x] == 1) return;
	a[x] = sqrt(a[x]);
	if (a[x] == 1) f[x] = find(fa(x));
} 
int solve(int x, int k) {
	if (k > m) return up(x, k);
	int y = find(fa(x));
	return up(y, (k - (depth[x] - depth[y]) % k) % k);
}
int solve2(int x, int y, int f, int k) {
	if (depth[y] - depth[f] >= k) return up(y, k);
	return up(x, depth[x] + depth[y] - (depth[f] << 1) - k);
}
void update(int x, int y, int k) {
	int f = lca(x, y), len = depth[x] + depth[y] - (depth[f] << 1);
	if (len % k) upd(y), y = solve2(x, y, f, len % k), f = lca(x, y);
	while (depth[x] >= depth[f]) upd(x), x = solve(x, k);
	while (depth[y] > depth[f]) upd(y), y = solve(y, k);
}
ll query(int x, int y, int k) {
	int f = lca(x, y), len = depth[x] + depth[y] - (depth[f] << 1);
	ll res = 0;
	if (len % k) res += a[y], y = solve2(x, y, f, len % k), f = lca(x, y);
	res += (depth[x] + depth[y] - (depth[f] << 1)) / k + 1;
	while (depth[x] >= depth[f]) res += a[x] - 1, x = solve(x, k);
	while (depth[y] > depth[f]) res += a[y] - 1, y = solve(y, k);
	return res; 
}
int main() {
	int i; n = rd(); m = sqrt(n);
	for (i = 1; i <= n; ++i) a[i] = rd();
	for (i = 1; i < n; ++i) {
		int u = rd(), v = rd();
		ae(u, v); ae(v, u);
	}
	dfs(1, 0);
	for (i = 1; i <= n; ++i) {
		f[i] = i;
		if (a[i] == 1) f[i] = fa(i);
	}
	q = rd();
	while (q--) {
		int opt = rd(), x = rd(), y = rd(), k = rd();
		if (opt) printf("%lldn", query(x, y, k));
		else update(x, y, k);
	}
	return 0;
}

 另一种解法，不过很复杂：    拒绝复制！！！！！（逃）

#include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #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&&i0)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]=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;
}