http://www.spoj.pl/problems/QTREE3/

OrzNOI的神犇们……原来7k+是GYZ大神 - - 我果断被神犇们华丽BS了……RP掉光了啊……

在被Tim大神（Orz！！）虐了以后我下定必死的决心去写了轻重边树链剖分。一开始想写QTREE结果边权把我弄得晕头转向（我果然是苣蒻），所以只能去写写QTREE3……QTREE3由于有一个点是定点，所以不用LCA了，代码奇短无比，比块状树还短啊……

由于剖的题解太多了……我就说几个trick罢……

1.所有的线段树（或者其他什么东西）保存在一个数组里，给每个点记录一个数据结构的起始位置就可以了。

2.DFS只需要一遍就可以了……第一部分求LCA||找重链，第二部分对轻链边的孩子们循环构链

3.建超级根

4.变量名尽量定义得规则一点……避免2掉

5.不能1Y就对拍去！！！线段树那个我没对拍调了六小时才发现BUG（对某个点下的每条轻链都要把初始位置调零……我画的树是颗二叉树于是我就二叉了）。堆那个我没对拍又调了一晚上（8个0……昨天晚上果然脑子进浆糊了），今天早上和线段树那个拍了拍半小时就找到问题了（删点的时候要更新a与d我只更新了a……）

就这样罢……贴我的2X代码……线段树的那个加了getint只有35行……堆的45行，主要是sink与float太长了唉。我看了看最快的代码5.05s……看来我的剖还是挺快的！

#include <stdio.h>
int n,m,a[262144],as=0,r[100001],f[100001],s[100001],l[100001],d[100001],pos[262144];
struct edge{struct edge *next;int y;}*map[100001],st[200000],*h[100001];
getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1;
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}void make(i){
	struct edge *p=map[i],*q;int k,dp;
	for(l[i]=s[i]=1;p;p=p->next)if(p->y!=f[i]){
		f[p->y]=i;make(p->y);s[i]+=s[p->y];
		if(i&&(!h[i]||s[h[i]->y]<s[p->y]))l[i]=l[(h[i]=p)->y]+1;
	}for(p=map[i];q=p;p=p->next)if(p->y!=f[i]&&p!=h[i]){
		for(k=p->y;l[k]!=(l[k]&-l[k]);l[k]+=l[k]&-l[k]);
		for(dp=0,as--;q;q=h[q->y])pos[(s[q->y]=as)+(l[q->y]=l[r[q->y]=k])+(d[q->y]=dp++)]=q->y;
		as+=l[k]<<1;
	}
}main(){
	int i,x,y;
	(map[0]=st)->y=1;n=getint();m=getint();
	for(i=n-1<<1;i;i-=2){
		st[i^1].y=x=getint();st[i].y=y=getint();
		st[i].next=map[x];st[i^1].next=map[y];
		map[x]=st+i;map[y]=st+(i^1);
	}for(make(0);m--&&(i=getint(),x=getint());)if(i){
		for(i=-1;x;x=f[r[x]])if(a[s[x]+1]){
			for(y=1;y<l[x];y=a[s[x]+(y<<1)]?y<<1:y<<1^1);
			if(y<=l[x]+d[x])i=pos[s[x]+y];
		}printf("%d\n",i);
	}else{
		i=a[s[x]+l[x]+d[x]]?-1:1;
		for(y=l[x]+d[x];y;y>>=1)a[s[x]+y]+=i;
	}return 0;
}

#include <stdio.h>
int n,m,a[100000],as=-1,r[100001],f[100001],s[100001],l[100001],d[100001],o[100001],de[100001];
struct edge{struct edge *next;int y;}*map[100001],st[200000],*h[100001];
getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1;
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}void make(i){
	struct edge *p=map[i],*q;
	for(l[i]=s[i]=1;p;p=p->next)if(p->y!=f[i]){
		f[p->y]=i;de[p->y]=de[i]+1;make(p->y);s[i]+=s[p->y];
		if(i&&(!h[i]||s[h[i]->y]<s[p->y]))l[i]=l[(h[i]=p)->y]+1;
	}for(p=map[i];q=p;p=p->next)if(p->y!=f[i]&&p!=h[i]){
		s[p->y]=as;as+=l[p->y];
		for(l[p->y]=0;q;q=h[q->y])s[q->y]=s[r[q->y]=p->y];
	}
}main(){
	int i,x,y,t1,t2,j;
	(map[0]=st)->y=1;n=getint();m=getint();
	for(i=n-1<<1;i;i-=2){
		st[i^1].y=x=getint();st[i].y=y=getint();
		st[i].next=map[x];st[i^1].next=map[y];
		map[x]=st+i;map[y]=st+(i^1);
	}for(make(0);m--&&(i=getint(),x=getint());)if(i){
		for(i=-1;x;x=f[r[x]])if(l[r[x]]&&de[a[s[x]+1]]<=de[x])i=a[s[x]+1];
		printf("%d\n",i);
	}else if(o[x]){
		for(i=d[a[s[x]+d[x]]=a[s[x]+l[r[x]]--]]=d[x];i<<1<=l[r[x]];i=j){
			j=i<<1==l[r[x]]?i<<1:de[a[s[x]+(i<<1)]]<de[a[s[x]+(i<<1^1)]]?i<<1:i<<1^1;
			if(de[a[s[x]+j]]>de[a[s[x]+i]])break;
			y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+j];a[t2]=y;
			y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y;
		}for(;i!=1&&(de[a[s[x]+(i>>1)]]>de[a[s[x]+i]]);i>>=1){
			y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+(i>>1)];a[t2]=y;
			y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y;
		}o[x]=0;
	}else{
		a[++l[r[x]]+s[x]]=x;
		for(i=d[x]=l[r[x]];i!=1&&de[a[s[x]+(i>>1)]]>de[a[s[x]+i]];i>>=1){
			y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+(i>>1)];a[t2]=y;
			y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y;
		}o[x]=1;
	}return 0;
}

• inline
• block