所谓的考试，就一定有一道绝版题使得男人沉默女人流泪，而不有理有据的绝版题怎么称得上绝版呢？ 火车国一开始只有一座城市，也就是1号城市。不过火车国的领土是在不断变化的，经常会新添加一个城市，那么小火车就会用一条铁路把它和某个老城市连接起来。 偶尔火车国会发生自然灾害，那么小火车就得找到一个合适的城市指挥赈灾，这个城市满足所有城市到其距离乘以城市人口的和最小，如果有不止一个最小的城市时小火车会选择距离1号城市最近的。 当然火车国人口也是不断变化的，也就是说有时候某个城市的人口会改变。现在小火车请你告诉他每次指挥赈灾应该选择的城市。
用LCT来维护会动的树。 怎么求带权重心呢？ 从1开始。 先看看是否要往1所在重链方向走，否则找到轻边中子树权值和最大的，看看是否往那边走。 在重链方向上走可以在splay上二分。 轻边子树权值和最大通过LCT+set维护虚边信息。 每次找到带权重心后access，这样复杂度就对了！因为虚实切换次数均摊n log n。
#include<cstdio> #include<algorithm> #include<set> #define fo(i,a,b) for(i=a;i<=b;i++) #define max(a,b) (a>b?a:b) using namespace std; typedef long long ll; const int maxn=300000+10; struct dong{ int x; ll y; friend bool operator <(dong a,dong b){ return a.y<b.y||a.y==b.y&&a.x<b.x; } } zlt; set<dong> s[maxn]; set<dong>::iterator it; ll mx[maxn],key[maxn],ad[maxn]; int a[maxn],size[maxn]; int father[maxn],tree[maxn][2],pp[maxn],sta[maxn]; int i,j,k,l,t,n,m,tot,top,ans,lastans,nans,de; ll sum; bool czy,gjx; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } int pd(int x){ return tree[father[x]][1]==x; } void update(int x){ mx[x]=key[x]; if (tree[x][0]) mx[x]=max(mx[x],mx[tree[x][0]]); if (tree[x][1]) mx[x]=max(mx[x],mx[tree[x][1]]); size[x]=size[tree[x][0]]+size[tree[x][1]]+1; } void rotate(int x){ int y=father[x],z=pd(x); father[x]=father[y]; if (father[y]) tree[father[y]][pd(y)]=x; tree[y][z]=tree[x][1-z]; if (tree[x][1-z]) father[tree[x][1-z]]=y; tree[x][1-z]=y; father[y]=x; if (pp[y]) pp[x]=pp[y],pp[y]=0; update(y); update(x); } void mark(int x,int v){ if (!x) return; key[x]+=(ll)v; mx[x]+=(ll)v; ad[x]+=(ll)v; } void down(int x){ if (ad[x]){ mark(tree[x][0],ad[x]); mark(tree[x][1],ad[x]); ad[x]=0; } } void remove(int x,int y){ top=0; while (x!=y){ sta[++top]=x; x=father[x]; } while (top) down(sta[top--]); } void splay(int x,int y){ remove(x,y); while (father[x]!=y){ if (father[father[x]]!=y) if (pd(x)==pd(father[x])) rotate(father[x]);else rotate(x); rotate(x); } } ll getkey(int x){ splay(x,0); return key[x]; } void real_empty(int x,int y){ splay(y,0); splay(x,y); tree[y][1]=0; update(y); father[x]=0; pp[x]=y; zlt.x=x;zlt.y=getkey(x); s[y].insert(zlt); } void empty_real(int x,int y){ splay(y,0); splay(x,0); tree[y][1]=x; update(y); father[x]=y; pp[x]=0; zlt.x=x;zlt.y=getkey(x); s[y].erase(s[y].find(zlt)); } void access(int x){ int y,z; splay(x,0); z=tree[x][1]; if (z){ while (tree[z][0]){ down(z); z=tree[z][0]; } splay(z,x); real_empty(z,x); } while (pp[x]){ y=pp[x]; splay(y,0); z=tree[y][1]; if (z){ while (tree[z][0]){ down(z); z=tree[z][0]; } splay(z,y); real_empty(z,y); } while (tree[x][0]){ down(x); x=tree[x][0]; } splay(x,0); empty_real(x,y); splay(x,0); } } void link(int x,int y){ pp[y]=x; zlt.x=y;zlt.y=getkey(y); s[x].insert(zlt); } int find(int x){ down(x); if (mx[tree[x][1]]>sum/2) return find(tree[x][1]); if (key[x]>sum/2) return x; else return find(tree[x][0]); } int main(){ freopen("jueban.in","r",stdin);freopen("jueban.out","w",stdout); mx[0]=-1000000000000000; czy=1; m=read();a[tot=1]=size[1]=read(); key[1]=mx[1]=sum=a[1]; while (m--){ t=read(); if (t==1){ j=read();k=read(); if (czy){ j^=lastans;k^=lastans; } ++tot; size[tot]=1; a[tot]=k; link(j,tot); access(tot); splay(tot,0); sum+=(ll)k; mark(tot,k); } else if (t==2){ j=read();k=read(); if (czy){ j^=lastans;k^=lastans; } access(j); splay(j,0); k=k-a[j]; a[j]+=k; sum+=(ll)k; mark(j,k); } else{ ans=1; while (1){ splay(ans,0); if (tree[ans][1]){ t=tree[ans][1]; while (tree[t][0]){ down(t); t=tree[t][0]; } splay(t,0); if (key[t]>sum/2){ splay(ans,0); ans=find(tree[ans][1]); continue; } } it=s[ans].end(); if (it==s[ans].begin()) break; it--; zlt=*it; if (zlt.y<=sum/2) break; ans=zlt.x; } access(ans); printf("%d\n",ans); lastans=ans; } //printf("%d\n",m); } }