题解【CF916E Jamie and Tree】很普通的 ETT
jerry3128
·
·
题解
Euler Tour Tree
- 这个能换根，并不是 splay 维护括号序那个简化版。
- 因为只有子树操作，并且维护的信息为和，具有交换律，那么 ETT 也就够对本题进行维护。
- 考虑使用 ETT 对本题的树进行维护，因为 ETT 自身是将一棵树拍平成欧拉环游序，对于树上一些树形结构的信息有损失。所以考虑使用一颗 LCT 对 ETT 的结构进行辅助维护。
- 我们只在代表节点维护一个节点的权值，因为没有 link 和 cut 操作，所以不涉及 ETT 上点的删除，故也不需要数据的转运，代码量大大减小。
- 换根就是区间平移，新根前面的欧拉序放在后面就行了，因为一个欧拉序就像一个圈把树圈起来，从哪里开始其实无伤大雅。
- 子树修改和查询直接定位子树区间信息就行了。
- 同时本题在 LCT 与 ETT 上，LCT 只对结构进行辅助，二者之间的操作并没有互相映射，所以复杂度仍然只有 O(\log n) 单次操作。
//ayame保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
#include<bits/stdc++.h>
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
return buf[p1++];
}
#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
long long ret=0,flag=1;
char c=gc();
while(c<'0'||c>'9') {
if(c=='-')flag=-1;
c=gc();
}
while(c<='9'&&c>='0') {
ret=(ret<<3)+(ret<<1)+c-'0';
c=gc();
}
return ret*flag;
}
void pc(char x) {
if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
wb[p2++]=x;
}
void wrt(long long x) {
if(x<0)pc('-'),x=-x;
int c[24]= {0};
if(!x)return pc('0'),void();
while(x)c[++c[0]]=x%10,x/=10;
while(c[0])pc(c[c[0]--]+'0');
}
int n,m;
vector<int> vec[100005];
int ind[200005],sign,vst[200005],rep[200005];
void dfs(int x,int prt){
ind[++sign]=x;
for(int y:vec[x])if(y^prt)dfs(y,x),ind[++sign]=x;
}
namespace LCT{
struct node {
int ch[2],fa,rev,pre,suf;
} v[100005];
bool isroot(int x){
return v[v[x].fa].ch[0]!=x&&v[v[x].fa].ch[1]!=x;
}
void tag_rev(int x) {
swap(v[x].ch[0],v[x].ch[1]);
swap(v[x].pre,v[x].suf);
v[x].rev^=1;
}
void push_down(int rt) {
if(v[rt].rev) {
tag_rev(v[rt].ch[0]);
tag_rev(v[rt].ch[1]);
v[rt].rev=0;
}
}
void push_up(int x){
v[x].pre=v[x].ch[0]?v[v[x].ch[0]].pre:x;
v[x].suf=v[x].ch[1]?v[v[x].ch[1]].suf:x;
}
void rot(int x) {
int p=v[x].fa,g=v[p].fa;
bool d=v[p].ch[1]==x;
if(!isroot(p))v[g].ch[v[g].ch[1]==p]=x;
v[p].ch[d]=v[x].ch[d^1];
v[v[x].ch[d^1]].fa=p;
v[x].ch[d^1]=p;
v[x].fa=g,v[p].fa=x;
push_up(p),push_up(x);
}
void pre_push_down(int x) {
if(!isroot(x))pre_push_down(v[x].fa);
push_down(x);
}
void splay(int x) {
pre_push_down(x);
while(!isroot(x)) {
int p=v[x].fa,g=v[p].fa;
if(!isroot(p))rot(v[g].ch[0]==p^v[p].ch[0]==x?x:p);
rot(x);
}
}
int access(int x) {
int ret=0;
for(int y=0;x;y=x,x=v[x].fa)
splay(x),v[x].ch[1]=y,push_up(ret=x);
return ret;
}
void makeroot(int x) {
access(x),splay(x),tag_rev(x);
}
void link(int x,int y) {
makeroot(y),v[y].fa=x;
}
void cut(int x){
access(x),splay(x),v[v[x].ch[0]].fa=0,v[x].ch[0]=0,push_up(x);
}
int ask(int x){
return access(x),splay(x),v[v[x].ch[0]].suf;
}
}
namespace ETT{
int root,tot;
map<int,int> e[100005];
struct node{
int ch[2],fa,id,sz,rep,pre,suf;
long long sum,val,stag;
}v[200005];
bool isroot(int x){
return v[v[x].fa].ch[0]!=x&&v[v[x].fa].ch[1]!=x;
}
void push_up(int x){
if(!x)return;
v[x].pre=v[x].ch[0]?v[v[x].ch[0]].pre:x;
v[x].suf=v[x].ch[1]?v[v[x].ch[1]].suf:x;
v[x].sz=v[v[x].ch[0]].sz+v[v[x].ch[1]].sz+v[x].rep;
v[x].sum=v[v[x].ch[0]].sum+v[v[x].ch[1]].sum+v[x].val;
}
void push_stag(int x,long long val){
if(!x)return;
v[x].sum=v[x].sum+v[x].sz*val,v[x].val=v[x].val+v[x].rep*val;
v[x].stag=v[x].stag+val;
}
void push_down(int x){
if(v[x].stag){
push_stag(v[x].ch[0],v[x].stag);
push_stag(v[x].ch[1],v[x].stag);
v[x].stag=0;
}
}
void pre_push_down(int rt){
if(v[rt].fa)pre_push_down(v[rt].fa);
push_down(rt);
}
int getpoint(int x,int lim=-1){
if(e[e[x].begin()->first][x]!=lim)return e[e[x].begin()->first][x];
return e[e[x].rbegin()->first][x];
}
int build(int l,int r){
int mid=(l+r)>>1,x=++tot;v[x].id=ind[mid];v[x].stag=0,push_up(x);
if(!vst[v[x].id])vst[v[x].id]=1,v[x].rep=1,rep[v[x].id]=x;
if(l<mid)v[x].ch[0]=build(l,mid-1),v[v[x].ch[0]].fa=x,e[v[v[v[x].ch[0]].suf].id][v[x].id]=x;
if(mid<r)v[x].ch[1]=build(mid+1,r),v[v[x].ch[1]].fa=x,e[v[x].id][v[v[v[x].ch[1]].pre].id]=v[v[x].ch[1]].pre;
return push_up(x),x;
}
void rot(int x){
int p=v[x].fa,g=v[p].fa;
bool d=v[p].ch[1]==x;
if(!isroot(p))v[g].ch[v[g].ch[1]==p]=x;
v[p].ch[d]=v[x].ch[d^1];
v[v[x].ch[d^1]].fa=p;
v[x].ch[d^1]=p;
v[p].fa=x,v[x].fa=g;
push_up(p),push_up(x);
}
void splay(int x,int f=0){
pre_push_down(x);
while(v[x].fa!=f){
int p=v[x].fa,g=v[p].fa;
if(g!=f)rot(v[g].ch[0]==p^v[p].ch[0]==x?x:p);
rot(x);
}
}
void makeroot(int x){
if(root==x)return;
LCT::makeroot(x),root=x,x=getpoint(x);
splay(x),splay(x=v[v[x].ch[1]].pre);
int y=v[x].ch[0];
v[y].fa=0,v[x].ch[0]=0,push_up(x);
splay(x=v[x].suf),v[x].ch[1]=y,v[y].fa=x,push_up(x);
}
void add(int x,long long val){
if(x==root)return splay(1),push_stag(1,val);
int prt=LCT::ask(x),l=e[prt][x],r=e[x][prt];
splay(l),splay(r,l);
v[l].val=v[l].val+v[l].rep*val,push_stag(v[r].ch[0],val);
push_up(r),push_up(l);
}
long long ask(int x){
if(x==root)return splay(1),v[1].sum;
int prt=LCT::ask(x),l=e[prt][x],r=e[x][prt];
splay(l),splay(r,l);
return (v[l].val+v[v[r].ch[0]].sum);
}
}
int main() {
// freopen("lct.in","r",stdin);
// freopen("lct.out","w",stdout);
n=getint(),m=getint(),ETT::root=1;
static int a[100005];
for(int i=1;i<=n;i++)a[i]=getint();
for(int i=1;i<n;i++){
int u=getint(),v=getint();
vec[u].push_back(v),vec[v].push_back(u);
LCT::link(u,v);
}
dfs(1,0),ETT::build(2,sign),LCT::makeroot(1);
ETT::splay(1),ETT::e[1][ETT::v[ETT::v[1].pre].id]=ETT::v[1].pre;
for(int i=1;i<=n;i++){
int x=ETT::getpoint(i);
ETT::splay(x),ETT::v[x].val=a[i],ETT::push_up(x);
}
for(int i=1;i<=m;i++){
int opt=getint();
if(opt==1)ETT::makeroot(getint());
if(opt==2){int x=getint(),y=getint();ETT::add((LCT::access(x),LCT::access(y)),getint());}
if(opt==3)wrt(ETT::ask(getint())),pc('\n');
}
fwrite(wb,1,p2,stdout);
return Loli Kon;
}