code:
#include <cstdio> #include <string> #include <cstring> #include <algorithm> using namespace std; const int N=200006; int cur_id; namespace IO { void setIO(string s) { string in=s+".in"; string out=s+".out"; freopen(in.c_str(),"r",stdin); // freopen(out.c_str(),"w",stdout); } }; namespace BIT { int C[N]; #define lowbit(t) (t&(-t)) void update(int x,int v) { for(int i=x;i<N;i+=lowbit(i)) C[i]+=v; } int query(int x) { int tmp=0; for(int i=x;i>0;i-=lowbit(i)) tmp+=C[i]; return tmp; } }; namespace LCT { #define lson t[x].ch[0] #define rson t[x].ch[1] #define get(x) (t[t[x].f].ch[1]==x) #define Isrt(x)(!(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x)) struct node { int ch[2],rev,f,size,id; }t[N]; int sta[N]; void Pushup(int x) { t[x].size=t[lson].size+t[rson].size+1; } void mark(int x) { t[x].rev^=1; swap(lson,rson); } void Pushdown(int x) { if(t[x].rev) { t[x].rev=0; if(lson) mark(lson); if(rson) mark(rson); } if(lson) t[lson].id=t[x].id; if(rson) t[rson].id=t[x].id; } void Rotate(int x) { int old=t[x].f; int fold=t[old].f; int which=get(x); if(!Isrt(old)) t[fold].ch[t[fold].ch[1]==old]=x; t[old].ch[which]=t[x].ch[which^1]; t[t[old].ch[which]].f=old; t[x].ch[which^1]=old; t[old].f=x; t[x].f=fold; Pushup(old); Pushup(x); } void Splay(int x) { int v=0,u=x,fa; for(sta[++v]=u;!Isrt(u);u=t[u].f) sta[++v]=t[u].f; for(;v;--v) Pushdown(sta[v]); for(u=t[u].f;(fa=t[x].f)!=u;Rotate(x)) { if(t[fa].f!=u) Rotate(get(fa)==get(x)?fa:x); } } void Access(int x) { for(int y=0;x;y=x,x=t[x].f) { Splay(x); rson=0; Pushup(x); BIT::update(t[x].id,-t[x].size); BIT::update(cur_id,t[x].size); rson=y; Pushup(x); } } void Move_Root(int x) { ++cur_id; Access(x),Splay(x),mark(x); t[x].id=cur_id; } }; int n,edges; int hd[N],to[N<<1],nex[N<<1]; int query(int x) { using namespace LCT; Splay(x); return BIT::query(t[x].id)-t[lson].size; } void add(int u,int v) { nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; } void dfs(int u,int ff) { } int main() { IO::setIO("input"); int i,j; return 0; }