# SPOJ 913 QTREE2 – Query on a tree II 题解【LCT】【splay】

## Description

You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3…N-1. Each edge has an integer value assigned to it, representing its length.

We will ask you to perfrom some instructions of the following form:

• DIST a b : ask for the distance between node a and node b
or
• KTH a b k : ask for the k-th node on the path from node a to node b

Example:
N = 6
1 2 1 // edge connects node 1 and node 2 has cost 1
2 4 1
2 5 2
1 3 1
3 6 2

Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6
DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5)
KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)

## Input

The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000)
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 100000)
• The next lines contain instructions “DIST a b” or “KTH a b k”
• The end of each test case is signified by the string “DONE“.

There is one blank line between successive tests.

## Output

For each “DIST” or “KTH” operation, write one integer representing its result.

Print one blank line after each test.

## Example

Input:
1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

Output:
5
3


## Code：

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
int ch[2][20100],fa[20100],lazy[20100];
int sz[20100],key[20100],sum[20100];
void pushdown(int k)
{
if(lazy[k])
{
lazy[k]=0;
int tmp=ls;
ls=rs;
rs=tmp;
lazy[ls]^=1;
lazy[rs]^=1;
}
}
void maintain(int k)
{
sum[k]=sum[ls]+key[k]+sum[rs];
sz[k]=sz[ls]+1+sz[rs];
}
void Rotate(int k)
{
int y=fa[k];
if(!isroot(y))
ch[which(y)][fa[y]]=k;
bool d=which(k);
fa[k]=fa[y];
fa[y]=k;
ch[d][y]=ch[!d][k];
fa[ch[d][y]]=y;
ch[!d][k]=y;
maintain(y);
maintain(k);
}
int stk[20100],tp=0;
void splay(int k)
{
while(!isroot(k))
{
stk[++tp]=k;
k=fa[k];
}
stk[++tp]=k;
while(tp)
pushdown(stk[tp--]);
k=stk[1];
while(!isroot(k))
{
int y=fa[k];
if(!isroot(y))
Rotate(which(k)^which(y)?k:y);
Rotate(k);
}
}
void access(int k)
{
for(int x=k,y=0;x;y=x,x=fa[x])
{
splay(x);
ch[1][x]=y;
maintain(x);
}
}
void makeroot(int k)
{
access(k);
splay(k);
lazy[k]^=1;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
splay(x);
}
{
makeroot(x);
fa[x]=y;
}
int Find(int k,int x)//k中第x大的元素
{
pushdown(k);
int L=sz[ls];
if(x<=L)
return Find(ls,x);
if(x==L+1)
return k;
return Find(rs,x-L-1);
}
char op[100];
int main()
{
int T,n,u,v,w;
scanf("%d",&T);
while(T--)
{
memset(ch,0,sizeof(ch));
memset(fa,0,sizeof(fa));
memset(lazy,0,sizeof(lazy));
memset(key,0,sizeof(key));
memset(sz,0,sizeof(sz));
memset(sum,0,sizeof(sum));
scanf("%d",&n);
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&u,&v,&key[n+i]);
sum[n+i]=key[n+i];
}
while(1)
{
scanf("%s",op);
if(op[1]=='O')
break;
scanf("%d%d",&u,&v);
if(op[0]=='K')
{
scanf("%d",&w);
split(u,v);
printf("%d\n",Find(u,(w<<1)-1));
}
else
{
split(u,v);
printf("%d\n",sum[u]);
}
}
puts("");
}
return 0;
}


### 1 说点什么

0 Followers

Most reacted comment