https://www.spoj.pl/problems/QTREE2/

用块状树水过QTREE以后就开始颓废于电影...今天花了一个小时终于A掉了QTREE2...

写的时候非常纠结...主要是结构体定义的变量多了一个老搞混...额

然后没有1Y就是个悲剧啊。st指针忘记初始化了！！！导致栈溢出！！！万一是比赛就OVER了！！！

方法是离线TARJAN求LCA。对于DIST直接输出dis[i]+dis[j]-2dis[lca[i,j]]。对于KTH则维护每个点向上1,2,4,8...个点，然后logn向上跳Orz...

TIP1:此题没有给出操作个数...我写的代码开了10000A了...可见操作数不是很多...N+Q还是挺合算的...

TIP2:logn向上跳这东西我用了个很久以前看到的二进制加速，即MultiplyDeBruijnBitPosition这个。具体可以看看M67大牛blog！

http://www.matrix67.com/blog/archives/3985

PS:谁来告诉我排名顶上那个0.15S的秒杀代码怎么写的...看MEM似乎是在线的啊。。在线的应该没离线的快啊...郁闷！

#include <stdio.h>
#define find(x) N[(unsigned)((((x)&(-(x)))*0x077CB531U))>>27]
static const int N[32]={0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9};
int n,qs[10000][4],qss,fmap[10000][14];
typedef struct _edge{struct _edge *next;int t,y;}edge;
edge map[10000],*tail[10000],starr[39998],qsmap[10000],*st;
fa(x){return qsmap[x].y==x?x:(qsmap[x].y=fa(qsmap[x].y));}
getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}void make(i,f){
	edge *p=map[i].next,*q=qsmap[i].next;
	for(qsmap[i].t=qsmap[f].t+1;q;q=q->next)if(qsmap[q->y].t!=-1)qs[q->t][3]=fa(q->y);
	for(fmap[i][0]=map[i].y=f;p;p=p->next)if(p->y!=f){
		map[p->y].t=map[i].t+p->t;
		make(p->y,i);qsmap[p->y].y=i;
	}
}main(){
	int x,t,y,i,c;
	for(c=getint(),n=getint();c--;c&&(n=getint())){
		for(st=starr+19998,i=0;i<n;i++)(tail[i]=map+i)->next=0;
		for(i=0;i<n-1;i++){
			x=getint()-1;
			(tail[x]=tail[x]->next=starr+(i<<1))->y=y=getint()-1;
			(tail[y]=tail[y]->next=starr+(i<<1^1))->y=x;
			tail[x]->next=tail[y]->next=0;
			tail[x]->t=tail[y]->t=getint();
		}for(qss=i=0;i<n;i++)(tail[i]=qsmap+i)->next=0,qsmap[qsmap[i].y=i].t=-1;
		for(getchar(),i=getchar();i!='O';getchar(),i=getchar()){
			qs[qss][0]=x=getint()-1;
			(tail[x]=tail[x]->next=st++)->y=qs[qss][1]=y=getint()-1;
			(tail[y]=tail[y]->next=st++)->y=x;
			tail[x]->next=tail[y]->next=0;
			tail[x]->t=tail[y]->t=qss;
			qs[qss++][2]=(i=='T'?getint():0)-1;
		}for(make(i=0,0);i<13;i++)for(t=0;t<n;t++)fmap[t][i+1]=fmap[fmap[t][i]][i];
		for(i=0;i<qss;i++){
			if(qs[i][2]==-1)printf("%d\n",map[qs[i][0]].t+map[qs[i][1]].t-(map[qs[i][3]].t<<1));
			else{
				x=qsmap[qs[i][0]].t-qsmap[qs[i][3]].t;
				y=qsmap[qs[i][1]].t-qsmap[qs[i][3]].t;
				qs[i][2]<=x?(t=qs[i][2],x=qs[i][0]):(t=x+y-qs[i][2],x=qs[i][1]);
				for(;t;t^=1<<y)x=fmap[x][y=find(t)];
				printf("%d\n",x+1);
			}
		}putchar('\n');
	}return 0;
}

• inline
• block