? ? 大家肯定都做过洛谷吧！
有一次一个朋友给我发了一道题，我看了后笑了。
?这么简单的题，我简简单单的回了一句：cout<<"Hello,World!";
过了一会朋友说不是这道题，随后把链接发给了我，我打开看了后才发现??
“一切并非这么简单”
那道题竟是这样的：你们可以看看，链接：Hello world! - 洛谷
?
呃呃呃呃呃呃呃呃~~~~~
朋友发到：你帮帮我吧！
我：你不做不行吗？？？
朋友：嘿，你不会了是吧，你个zz；
我：已急；
我一会胳膊，开干！
此题的代码：? ? ?拒绝复制！！！！！！
#include <bits/stdc++.h>
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("%lld\n", query(x, y, k));
else update(x, y, k);
}
return 0;
}
?另一种解法，不过很复杂：? ? 拒绝复制！！！！！（逃）
#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;
}