[SPOJ913 QTREE2]LCA、DFS

【题目大意】
给出一棵带权的树。有两种询问。
1、问节点a到结点b路径的权和。
2、问节点a到结点b路径中第k个点是哪个。
【算法分析】
直接搞个RMQ来算LCA。
对于询问1，轻松得出ans=dist[a]+dist[b]-dist[LCA(a,b)]
对于询问2，按照a和b到LCA(a,b)的距离，可以判断他在LCA到a的链上还是到b的链上。
进一步转化为询问(x,y)：x上根走y步到达哪一个节点。
我们先把询问都放进链表里，然后一次记录路径的DFS，轻松解决。
【其他】1A
【CODE】
#include #include #include const int N=10005;
const int QQ=1000000;
struct edge{int y,w;edge *next;}space[N*2],*ls[N],Qspace[QQ],*Qls[N];
int n,e,Tc,Qe,tot,Qn;
int dist[N],dep[N],list[N*2],R[N],ans[QQ];
int rmq_node[17][N*2],rmq_dep[17][N*2],lg[N*2];

void addedge(int x,int y,int w){
space[++e].y=y; space[e].w=w;
space[e].next=ls[x]; ls[x]=&space[e];
}

void predfs(int p,int fa){
list[++tot]=p;
R[p]=tot;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
dist[t->y]=dist[p]+t->w;
dep[t->y]=dep[p]+1;
predfs(t->y,p);
list[++tot]=p;
}
}

void buildrmq(){
for (int i=1;i<=tot;i++){
rmq_node[0][i]=list[i];
rmq_dep[0][i]=dep[list[i]];
}
for (int k=1;1< for (int i=1;i+(1< if (rmq_dep[k-1][i] rmq_dep[k][i]=rmq_dep[k-1][i];
rmq_node[k][i]=rmq_node[k-1][i];
}else{
rmq_dep[k][i]=rmq_dep[k-1][i+(1< rmq_node[k][i]=rmq_node[k-1][i+(1< }
}

void init(){
e=0; memset(ls,0,sizeof(ls));
Qn=0; Qe=0; memset(Qls,0,sizeof(Qls));
scanf("%d",&n);
for (int i=1,x,y,w;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
addedge(y,x,w);
}
dist[1]=0; dep[1]=0; tot=0;
predfs(1,0);
buildrmq();
}

void addquestion(int x,int y){
Qspace[++Qe].y=y; Qspace[Qe].next=Qls[x]; Qls[x]=&Qspace[Qe];
Qspace[Qe].w=Qn;
}

int LCA(int l,int r){
if (l>r){
int tmp=l; l=r; r=tmp;
}
int k=lg[r-l+1];
if (rmq_dep[k][l] return rmq_node[k][l];
else
return rmq_node[k][r-(1<}

void build_question(){
char op[100];
int x,y,k,p;
for (Qn=1;;Qn++){
scanf("%s",op+1);
if (op[1]==’D’ && op[2]==’O’){
Qn–;
break;
}
if (op[1]==’D’){
scanf("%d%d",&x,&y);
p=LCA(R[x],R[y]);
ans[Qn]=dist[x]-2*dist[p]+dist[y];
}
else{
scanf("%d%d%d",&x,&y,&k);
p=LCA(R[x],R[y]);
if (dep[x]-dep[p]+1==k) ans[Qn]=p;
else if (k else addquestion(y,dep[y]-dep[p]-(k-(dep[x]-dep[p]+1)));
}
}
}

void solve(int p,int fa){
list[++tot]=p;
for (edge *q=Qls[p];q;q=q->next)
ans[q->w]=list[tot-q->y];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) solve(t->y,p);
tot–;
}

int main(){
lg[1]=0;
for (int i=2;i lg[i]=lg[i-1];
if (1< }
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
init();
build_question();
tot=0;
solve(1,0);
for (int j=1;j<=Qn;j++) printf("%dn",ans[j]);
}
}