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

点击量：3355

稍微利用了splay技巧的一道lct题目。

目录

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

题意

给定一棵树，边有边权。需要查询$ a\rightarrow b$路径上边权之和，或者查询$ a\rightarrow b$路径上的第$k$个点的编号。（此时$ a\rightarrow b$有向）

题解：

树剖太长了我们来用lct吧说实话lct写起来真的是太爽了。其实是板子太好背了

第一种操作，查询两点之间路径的边权和，这个直接化点为边，提取出$ (u,v)$这条链，splay查询区间和就可以了。

化点为边的操作在这篇博客里讲的有。

第二种操作，同样提取出$ (u,v)$这条链，因为链上的点总是点-边-点-……-点-边-点，那么第$ k$个点在平衡树上的相对大小就是$ 2k-1$。

但是find之前一定要先pushdown，不然的话相对大小会搞错造成答案错误。

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);
}
void link(int x,int y)
{
    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];
            link(u,n+i);
            link(v,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;
}