題目描述
16~83%
不會
100%
用LCT維護樹的形态，access後往上跳來找lca
之後用dfs序+線段樹維護權值和
其實正解就是直接用lca随便搞搞
話說我已經變成無(sha)腦(bi)資料結構選手了嗎。。。
code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define N 300000
using namespace std;
int fa[N+];
int ch[N+][];
bool rev[N+];
bool isroot[N+];
long long tr[*N+][];
int a[N+N+][];
int ls[N+];
int w[N+];
int st[N+];
int ed[N+];
int n,Q,i,j,k,l,type,len,root;
long long Find,x,y,z,ans,p;
void New(int x,int y)
{
len++;
a[len][]=y;
a[len][]=ls[x];
ls[x]=len;
}
void swap(int &x,int &y)
{
int z=x;
x=y;
y=z;
}
void init(int fa,int t)
{
int i;
st[t]=++j;
for (i=ls[t]; i; i=a[i][])
if (a[i][]!=fa)
init(t,a[i][]);
ed[t]=j;
}
void down(int t)
{
if (rev[t])
{
swap(ch[t][],ch[t][]);
rev[ch[t][]]^=;
rev[ch[t][]]^=;
rev[t]=;
}
}
void rot(int t)
{
if (isroot[t]) return;
int Fa=fa[t];
int x=(ch[Fa][]==t);
ch[Fa][x]=ch[t][x^];
fa[ch[t][x^]]=Fa;
ch[t][x^]=Fa;
fa[t]=fa[Fa];
fa[Fa]=t;
isroot[t]=isroot[Fa];
isroot[Fa]=;
if (!isroot[t])
ch[fa[t]][ch[fa[t]][]==Fa]=t;
}
void splay(int t)
{
while (!isroot[t])
{
down(fa[fa[t]]);
down(fa[t]);
down(t);
if (isroot[fa[t]])
rot(t);
else
if ((ch[fa[fa[t]]][]==fa[t]) ^ (ch[fa[t]][]==t))
rot(t),rot(t);
else
rot(fa[t]),rot(t);
}
}
void access(int t)
{
int x=;
while (t)
{
splay(t);
down(t);
isroot[ch[t][]]=;
isroot[x]=;
ch[t][]=x;
x=t;
t=fa[t];
}
}
void moveroot(int t)
{
access(t);
splay(t);
root=t;
rev[t]=;
down(t);
}
void link(int x,int y)
{
moveroot(y);
fa[y]=x;
}
void Down(int t,int len)
{
tr[t][]+=tr[t][]*len;
if (len>)
{
tr[t*2][]+=tr[t][];
tr[t*2+][]+=tr[t][];
}
tr[t][]=;
}
void change(int t,int l,int r,int x,int y,int s)
{
int mid=(l+r)/;
if (x<=l && r<=y)
{
tr[t][]+=s;
Down(t,r-l+);
return;
}
Down(t,r-l+);
if (x<=mid)
change(t*2,l,mid,x,y,s);
if (mid<y)
change(t*2+,mid+,r,x,y,s);
Down(t*2,mid-l+);
Down(t*2+,r-mid);
tr[t][]=tr[t*2][]+tr[t*2+][];
}
void find(int t,int l,int r,int x,int y)
{
int mid=(l+r)/;
Down(t,r-l+);
if (x<=l && r<=y)
{
Find+=tr[t][];
return;
}
if (x<=mid)
find(t*2,l,mid,x,y);
if (mid<y)
find(t*2+,mid+,r,x,y);
}
bool pd(int x,int y) {return ((st[x]<=st[y]) && (ed[y]<=ed[x]));}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d%d",&n,&Q);
fo(i,,n)
{
scanf("%d",&w[i]);
isroot[i]=;
}
fo(i,,n)
{
scanf("%d%d",&x,&y);
link(x,y);
New(x,y);
New(y,x);
}
j=;
init(,);
fo(i,,n)
change(,,n,st[i],st[i],w[i]);
moveroot();
for (;Q;Q--)
{
scanf("%d",&type);
switch (type)
{
case :
{
scanf("%lld",&x);
moveroot(x);
break;
}
case :
{
scanf("%lld%lld%lld",&x,&y,&z);
access(x);
i=y;
while (i)
{
p=i;
while (!isroot[i])
i=fa[i];
i=fa[i];
}
if (p==root)
{
tr[][]+=z;
Down(,n);
}
else
if (pd(p,root))
{
int P=p;
tr[][]+=z;
Down(,n);
access(p);
if (!ch[p][] && !ch[p][])
p=fa[p];
else
{
if (ch[p][])
i=; else i=;
p=ch[p][i];
down(p);//考試時沒加上這個
i^=;
while (ch[p][i])
{
p=ch[p][i];
down(p);//考試時沒加上這個
}
}
change(,,n,st[p],ed[p],-z);
}
else
change(,,n,st[p],ed[p],z);
break;
}
case :
{
moveroot(root);
ans=;
scanf("%lld",&p);
if (p==root)
{
Down(,n);
ans=tr[][];
}
else
if (pd(p,root))
{
Down(,n);
ans=tr[][];
access(p);
if (!ch[p][] && !ch[p][])
p=fa[p];
else
{
if (ch[p][])
i=; else i=;
p=ch[p][i];
down(p);//考試時沒加上這個
i^=;
while (ch[p][i])
{
p=ch[p][i];
down(p);//考試時沒加上這個
}
}
Find=;
find(,,n,st[p],ed[p]);
ans-=Find;
}
else
{
Find=;
find(,,n,st[p],ed[p]);
ans=Find;
}
printf("%lld\n",ans);
break;
}
}
}
fclose(stdin);
fclose(stdout);
return ;
}
後記
考試時因為沒下傳标記爆掉。。。
沒錯這是同一個程式
O2真神(sha)奇(bi)