题解 P4004 【Hello world!（helloworld）】
消失的海岸线
·
·
题解
丢个博客链接。。
这题打 LOJ 的 VP 的时候写暴力+卡常拿了 83分...
其实 YY 出做法是不困难的，考虑维护深度模 K 意义下相同的节点，建 K 颗树即可。
对于修改操作，用并查集将都是 $1$ 的串起来即可，开方 $log$ 次就变成 $1$ 了，和花神游历各国那题是一样的。
然后就没了...
结果巨不好写...
不要问我复杂度分析和块大小多大比较优...详细一点的可以看官方题解，贴个代码（逃
```cpp
#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;
}
```