【GDOI2017第四轮模拟day2】绝版题

本文主要是介绍【GDOI2017第四轮模拟day2】绝版题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

对于一棵树，q个操作可以新增节点或改变一个点的权值，或询问整棵树的带权重心，强制在线
$1\le q\le 3\times 10^5$

题解

考虑如何找带权重心，显然是每次往最大权的子树走，条件是这个子树的权×2大于整棵树的权值和。
那么就很明显了，我们要做的是维护以每个点为根的子树的权值和，以及每个点的儿子中的最大权。
由于一条链上的信息更改会影响很多点，那么我们可以用LCT，维护的是以每个点为根的子树的权值和，以及每个点的虚边儿子中的最大权。
对于后者，可以对每个点开一个set，在断开和连起来的时候都更改一下就好了
找答案的时候，我们考虑从根节点开始，每次在链上二分出要走到的位置，然后再走到他的最大儿子。
这样的复杂度貌似很悬？
我们这样做其实相当于从根走到重心，这根重心做一次access的复杂度是一样的，所以总的时间复杂度是 $O(n log^2 n)$

Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;
typedef double db;int get(){char ch;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-'){int s=0;while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return -s;}int s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return s;
}const int N = 300010;struct light_edge{int x;LL s;friend bool operator <(light_edge a,light_edge b){if (a.s!=b.s)return a.s>b.s;return a.x<b.x;}
};
set<light_edge>s[N];
struct point{int s[2],val,ad,tot;LL sum,mv;
}tree[N];
int fa[N];
int n;
int m;
int a[N],k;
LL val[N];
int w[N];LL maxll(LL x,LL y){if (x>y)return x;return y;
}void update(int x){tree[x].tot=tree[tree[x].s[0]].tot+tree[tree[x].s[1]].tot+1;tree[x].mv=maxll(tree[tree[x].s[0]].mv+tree[x].ad,maxll(tree[tree[x].s[1]].mv+tree[x].ad,tree[x].sum));
}void down(int x){if (tree[x].ad!=0){int y=tree[x].s[0];if (y){tree[y].sum=tree[y].sum+tree[x].ad;tree[y].mv=tree[y].mv+tree[x].ad;tree[y].ad=tree[y].ad+tree[x].ad;}y=tree[x].s[1];if (y){tree[y].sum=tree[y].sum+tree[x].ad;tree[y].mv=tree[y].mv+tree[x].ad;tree[y].ad=tree[y].ad+tree[x].ad;}tree[x].ad=0;}update(x);
}int pd(int x){if (tree[fa[x]].s[0]==x)return 0;if (tree[fa[x]].s[1]==x)return 1;return -1;
}void clear(int x){k=0;for(;pd(x)!=-1;x=fa[x])a[++k]=x;a[++k]=x;fd(i,k,1)down(a[i]);
}void rotate(int x){int y=fa[x],z=fa[y];int tx=pd(x),ty=pd(y);if (ty!=-1)tree[z].s[ty]=x;fa[x]=z;if (tree[x].s[tx^1])fa[tree[x].s[tx^1]]=y;fa[y]=x;tree[y].s[tx]=tree[x].s[tx^1];tree[x].s[tx^1]=y;update(y);update(x);if (ty!=-1)update(z);
}void splay(int x){clear(x);while(pd(x)!=-1){if (pd(fa[x])!=-1){if (pd(fa[x])==pd(x))rotate(fa[x]);else rotate(x);}rotate(x);}
}int get1st(int x){if (!x)return 0;down(x);if (tree[x].s[0])return get1st(tree[x].s[0]);return x;
}void put_light(int x,int y,LL sum){fa[y]=x;light_edge u;u.x=y;u.s=sum;s[x].insert(u);if (sum>val[x]){val[x]=sum;w[x]=y;}
}void del_light(int x,int y,LL sum){light_edge u;u.x=y;u.s=sum;s[x].erase(u);set<light_edge>::iterator h=s[x].begin();if (h!=s[x].end()){w[x]=(*h).x;val[x]=(*h).s;}else val[x]=w[x]=0;
}void split(int x,int y){splay(y);splay(x);tree[x].s[1]=0;update(x);put_light(x,y,tree[y].sum);
}void merge(int x,int y){splay(y);del_light(x,y,tree[y].sum);tree[x].s[1]=y;update(x);
}void access(int x){splay(x);if (tree[x].s[1])split(x,get1st(tree[x].s[1]));while(fa[x]){int y=fa[x];splay(y);if (tree[y].s[1])split(y,get1st(tree[y].s[1]));merge(y,get1st(x));splay(x);}
}void walk(int &x){x=w[x];}int kth(int x,int k){if (k>tree[x].tot)return 0;if (k<=tree[tree[x].s[0]].tot)return kth(tree[x].s[0],k);if (k==tree[tree[x].s[0]].tot+1)return x;return kth(tree[x].s[1],k-tree[tree[x].s[0]].tot-1);
}int getw(int x){down(x);if (tree[x].s[1]&&tree[tree[x].s[1]].mv*2>tree[1].sum)return getw(tree[x].s[1]);if (tree[x].sum*2>tree[1].sum)return x;if (tree[x].s[0]&&tree[tree[x].s[0]].mv*2>tree[1].sum)return getw(tree[x].s[0]);return x;
}int ans;void getans(){int x=1;ans=1;LL tv=1e+13;bool bz=1;while(bz&&x){bz=0;splay(x);int w=getw(x);splay(w);int u=get1st(tree[w].s[1]);LL tmp=maxll(val[w],maxll(tree[u].sum,tree[1].sum-tree[w].sum));if (tmp<tv){tv=tmp;ans=w;x=w;walk(x);bz=1;}if (u){splay(u);w=get1st(tree[u].s[1]);tmp=maxll(val[u],maxll(tree[w].sum,tree[1].sum-tree[u].sum));if (tmp<tv){tv=tmp;ans=u;x=u;walk(x);bz=1;}}}printf("%d\n",ans);
}int main(){freopen("jueban.in","r",stdin);freopen("jueban.out","w",stdout);m=get();tree[n=1].val=tree[1].sum=get();ans=0;fo(cas,1,m){int ty=get();if (ty==1){int x=get(),t=get();x^=ans;t^=ans;tree[++n].val=tree[n].sum=t;fa[n]=x;access(x);splay(x);tree[x].ad=tree[x].ad+t;tree[x].sum=tree[x].sum+t;put_light(x,n,t);update(x);}if (ty==2){int x=get(),t=get();x^=ans;t^=ans;access(x);splay(x);tree[x].ad=tree[x].ad+t-tree[x].val;tree[x].sum=tree[x].sum+t-tree[x].val;tree[x].val=t;update(x);}if (ty==3)getans();}fclose(stdin);fclose(stdout);return 0;
}