【题意】给定一棵带点权树，三种操作：
1.询问点x到根的路径和
2.子树x内的点权加定值y
3.将点x的父亲更换为y，保证仍是树。
【算法】平衡树（fhq-treap）
【题解】
将树的dfs序作为序列维护，对每个点入栈+1，出栈-1，这样操作1就是前缀和（非此路径的都会正负抵消），操作2就是区间加值，操作3就是区间移动，可以用平衡树维护。
具体实现：原树上每个点在序列中对应两个点（入栈和出栈），每个点维护自身系数（1或-1），自身数值（含系数），系数和，数值和。维护系数是为了满足通过标记直接修改sum。
还有一个问题，只知道点的编号如何查询点的排名，实际上就是左子树+往上左走时的所有左子树（均含本点）。
过程中，在up处更新左右节点的父亲即可，但要额外更新分裂合并时根节点的父亲。
记得开long long。
#include#include #include #include #define ll long longusing namespace std;const int maxn=400010;struct cyc{ int l,r,rnd,sz,fa,gnum,gsum;ll delta,num,sum;}t[maxn];struct edge{ int v,from;}e[maxn];int tote=0,first[maxn];void insert(int u,int v){tote++;e[tote].v=v;e[tote].from=first[u];first[u]=tote;}int n,m,be[maxn],ed[maxn],tot,a[maxn],b[maxn],c[maxn],st[maxn],root;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}void dfs(int x){ be[x]=++tot;b[tot]=1;c[tot]=a[x]; for(int i=first[x];i;i=e[i].from){ dfs(e[i].v); } ed[x]=++tot;b[tot]=-1;c[tot]=-a[x];}void up(int k){ t[k].sz=1+t[t[k].l].sz+t[t[k].r].sz; t[k].gsum=t[k].gnum+t[t[k].l].gsum+t[t[k].r].gsum; t[k].sum=t[k].num+t[t[k].l].sum+t[t[k].r].sum; if(t[k].l)t[t[k].l].fa=k; if(t[k].r)t[t[k].r].fa=k;}void modify(int k,int x){t[k].num+=1ll*t[k].gnum*x;t[k].sum+=1ll*t[k].gsum*x;t[k].delta+=x;}void down(int k){ if(t[k].delta){ modify(t[k].l,t[k].delta);modify(t[k].r,t[k].delta); t[k].delta=0; }}void DFS(int k){ if(!k)return; DFS(t[k].l);DFS(t[k].r); up(k);}void build(){ int top=0; for(int i=1;i<=tot;i++){ t[i]=(cyc){ 0,0,rand(),1,0,b[i],b[i],0,c[i],c[i]}; while(top&&t[st[top]].rnd>t[i].rnd){ t[st[top]].r=t[i].l; t[i].l=st[top--]; } t[st[top]].r=i; st[++top]=i; } t[0]=(cyc){ 0,0,0,0,0,0,0,0,0}; DFS(root=st[1]); t[root].fa=0;}int find(int x){ int sum=t[t[x].l].sz+1; while(t[x].fa!=0){ if(t[t[x].fa].r==x)sum+=t[t[t[x].fa].l].sz+1; x=t[x].fa; } return sum;}int merge(int a,int b){ if(!a||!b)return a^b; if(t[a].rnd