ZOJ 3522 Hide and seek

ZOJ 3522 Hide and seek

题目大意：大小姐与二小姐玩捉迷藏。红魔馆里有N（1<=N<=50000）个可以
来躲的地方，N-1条双向边连接所有的地方（就是一棵树），芙兰有100000
组询问问如果X,Y之间添加一条长度为L的边，树上所有点到X最短距离变化值
与到Y变化值之和。
看到这题题面跟东方有关就做了……咱用LCT做的。维护一大堆迷之变量： 虚儿
子大小的总和num，所在子树大小siz，所在splay子树上边权和sum，以及
（难以描述）ran和lan。
对于求所有点到t点的距离，先把t点提到根，再把新加的边连到的s点access一
下，在原本的路径上找到一个点p，使得t从原路径到p的距离与t从新路径到p
距离基本相等。认为p点以下的点都受到了新加边的影响，所以每个点认为对
答案造成了（s到t原路径长度-新路径长度）的影响。由于每个点的影响由于位
置不同，会有一些差值。lan和ran就是记录这个差值的。

在把t提到根节点的过程中，边权不太好维护。看到一种方法，就是把边视为
权值为L但不计入siz和num的点，而正常点的权值为0。感到学习到了非常棒
的姿势……
写这个玩意错了好多次，问题主要在找p点和long long……果然咱还是太弱
了。

细节还是有点多，得注意下。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100100;
int n;
int wea;
int stk[maxn],top;
int beg[maxn],w[maxn<<2][3],e;
void putin(int s,int t,int v)
{w[++e][0]=t;w[e][1]=beg[s];beg[s]=e;w[e][2]=v;
}
struct LCT{long long l[maxn],r[maxn],f[maxn],rev[maxn],siz[maxn],sum[maxn],num[maxn],lan[maxn],ran[maxn],val[maxn];void csh(){memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(f,0,sizeof(f));memset(rev,0,sizeof(rev));memset(lan,0,sizeof(lan));memset(ran,0,sizeof(ran));memset(siz,0,sizeof(siz));memset(num,0,sizeof(num));memset(beg,0,sizeof(beg));memset(val,0,sizeof(val));e=0;}bool isroot(int h){if(!f[h])return 1;if(l[f[h]]==h||r[f[h]]==h)return 0;return 1;}void push_down(int h){if(!rev[h]) return;long long tmp;tmp=l[h];l[h]=r[h];r[h]=tmp;rev[l[h]]^=1;rev[r[h]]^=1;rev[h]=0;swap(lan[h],ran[h]);   //开始tmp是int,害咱错了好⑨}void push_up(int h){if(h==0) return;push_down(h);push_down(l[h]);push_down(r[h]);//这里的push_down（似乎）很重要siz[h]=siz[l[h]]+siz[r[h]]+num[h];sum[h]=sum[l[h]]+sum[r[h]]+val[h];lan[h]=lan[r[h]] + (sum[l[h]]+val[h])*siz[r[h]] + sum[l[h]]*num[h] + lan[l[h]];ran[h]=ran[l[h]] + (sum[r[h]]+val[h])*siz[l[h]] + sum[r[h]]*num[h] + ran[r[h]];}//看push_up基本就可以理解lan和ran的含义了void rotate(int h){int fa=f[h],gfa=f[fa];if(fa==l[gfa]) l[gfa]=h;else if(fa==r[gfa]) r[gfa]=h;f[h]=gfa;if(h==l[fa]){l[fa]=r[h];f[r[h]]=fa;r[h]=fa;f[fa]=h;}else{r[fa]=l[h];f[l[h]]=fa;l[h]=fa;f[fa]=h;}push_up(fa);push_up(h);push_up(gfa);}void splay(int h){int fa,gfa;top=1;stk[top]=h;for(int pos=h;!isroot(pos);pos=f[pos])stk[++top]=f[pos];while(top){push_down(stk[top]);top--;}//printf("%d %dn",sum[h],f[h]);while(!isroot(h)){fa=f[h];//if(wea==2){printf("?n");system("pause");}if(isroot(fa)){rotate(h);return;}gfa=f[fa];if((h==l[fa])^(fa==l[gfa])){rotate(h);rotate(h);}else{rotate(fa);rotate(h);}}}void access(int x){int s=0;while(x){splay(x);num[x]+=siz[r[x]];r[x]=s;num[x]-=siz[r[x]];push_up(x);s=x;x=f[x];}}void makeroot(int x){access(x);splay(x);rev[x]^=1;}int findv(int u,long long v){int st=0;while(u){push_down(u);if((val[u]+sum[l[u]])*2<=v){st=u;v-=(val[u]+sum[l[u]])*2;u=r[u];}elseu=l[u];}return st;}//这个写法的find好像快一些void dfs_bt(int u){int v;if(u<=n) siz[u]=1;else siz[u]=0;for(int i=beg[u];i;i=w[i][1]){v=w[i][0];if(v==f[u])continue;f[v]=u;dfs_bt(v);siz[u]+=siz[v];}num[u]=siz[u];}void printh(int h){push_down(h);if(l[h]) printh(l[h]);cerr<<h<<" ";if(r[h]) printh(r[h]);}void printd(int h){push_down(h);if(l[h]) printd(l[h]);if(r[h]) printd(r[h]);}//调试用
}lct;
long long work(int s,int t,long long v)
{if(s==t) return 0;lct.makeroot(t);lct.access(s);lct.splay(s);long long tt=lct.sum[s];if(v>=tt) return 0;int p=lct.findv(s,tt+v);if(!p) return 0;lct.splay(p);lct.push_down(p);lct.push_down(lct.r[p]);long long cnt=lct.siz[lct.r[p]];return cnt*(tt-v)-lct.ran[lct.r[p]]*2;
}
int main(){
//  freopen(&#","r",stdin);
//  freopen(&#","w",stdout);int Q;int s,t;long long v;long long ans1,ans2;while(scanf("%d",&n)!=EOF){lct.csh();for(int i=1;i<=n-1;i++){scanf("%d%d%lld",&s,&t,&v);lct.val[n+i]=lct.sum[n+i]=v;putin(s,n+i,v);putin(n+i,s,v);putin(t,n+i,v);putin(n+i,t,v);//把边当做点}lct.dfs_bt(1);scanf("%d",&Q);while(Q--){scanf("%d%d%lld",&s,&t,&v);ans2=work(t,s,v);ans1=work(s,t,v);printf("%lldn",ans1+ans2);}}return 0;
}