文档章节

SPOJ QTREE2 (LCA - 倍增 在线)

o
 osc_z1hvg4cu
发布于 2018/04/24 22:25
字数 809
阅读 8
收藏 0

精选30+云产品,助力企业轻松上云!>>>

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). ttest 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 ab 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

思路:
倍增裸题。。。套板子,
求第k个的时候需要处理下,其他没什么。,。
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 2e5+10;
int dist[M],p[M][30],dep[M],head[M];
int cnt1,n;

struct node{
    int to,next,w;
}e[M];

void add(int u,int v,int w){
    e[++cnt1].w=w;e[cnt1].to=v;e[cnt1].next=head[u];head[u]=cnt1;
    e[++cnt1].w=w;e[cnt1].to=u;e[cnt1].next=head[v];head[v]=cnt1;
}

void dfs(int u){
    for(int i = head[u];i != -1;i=e[i].next){
        int v = e[i].to;
        if(v == p[u][0]) continue;
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + e[i].w;
        p[v][0] = u; //p[i][0]存i的父节点
        dfs(v);
    }
}

void init(){
    for(int j = 1;(1<<j)<=n;j++){
        for(int i = 1;i <= n;i++){
            p[i][j] = p[p[i][j-1]][j-1];
            //cout<<i<<" "<<j<<" "<< p[i][j]<<endl;
        }
    }
}

int lca(int a,int b){
    if(dep[a] > dep[b]) swap(a,b);
    int h = dep[b] - dep[a]; //h为高度差
    for(int i = 0;(1<<i)<=h;i++){  //(1<<i)&f找到h化为2进制后1的位置,移动到相应的位置
        if((1<<i)&h) b = p[b][i];
        //比如h = 5(101),先移动2^0祖先,然后再移动2^2祖先
    }
    //cout<<a<<" "<<b<<endl;
    if(a!=b){
        for(int i = 22;i >= 0;i --){
            if(p[a][i]!=p[b][i]){  //从最大祖先开始,判断a,b祖先,是否相同
                a = p[a][i]; b = p[b][i]; //如不相同,a,b,同时向上移动2^j
            }
        }
        a = p[a][0]; //这时a的father就是LCA
    }
    return a;
}

int kth(int u,int k){
    for(int i = 0;i < 22;i ++)
        if(k >> i&1)
            u = p[u][i];
    return u;
}

int main()
{
    int t,u,v,w,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cnt1 = 0;
        //init();
        memset(head,-1,sizeof(head));
        for(int i = 0;i < n-1;i ++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        dfs(1);
        init();
        char s[10];
        while(scanf("%s",s)!=EOF){
            if(s[1]=='O') break;
            scanf("%d%d",&u,&v);
            int num = lca(u,v);
            if(s[1]=='I'){
                printf("%d\n",dist[u]+dist[v]-2*dist[num]);
            }
            if(s[1]=='T'){
                scanf("%d",&k);
                int x = dep[u] - dep[num];
                if(x + 1 >= k)
                    printf("%d\n",kth(u,k-1));
                else printf("%d\n",kth(v,dep[v]+dep[u]-2*dep[num]+1-k));
            }
        }
    }
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

平时使用的Lszrz到底是什么协议?说说Xmodem/Ymodem/Zmodem

XMODEM, YMODEM, and ZMODEM 由于平时使用rz/sz较多,r/s好理解,一个send一个receive。但是由不太清楚z是什么意思,故有此文。 sx/rx, sb/rb (b=batch)和sz/rz分别实现了xmodem,ymodem和z...

独钓渔
今天
17
0
真正的强智能时代已经到来。道翰天琼认知智能机器人平台API大脑。

最近,我常说人工智能的寒冬快要来了,提醒业界要做好思想准备,但同时我也说:冬天来了,春天就不会远了…… 2019年6月我写了篇文章《深度学习的问题究竟在哪?》,说到深度学习的一个主要问...

jackli2020
今天
24
0
什么是控制型人格,控制型人格的筛查测试

一、 什么是控制性人格 拥有控制型人格的人,他们会尽力的隐藏自己的意图,但是又会使用很微妙的方式来利用周围人的弱点,进而占取便宜时,使他们能够得到自己想要的东西。这类人的控制欲非常...

蛤蟆丸子
今天
14
0
【Spring】Spring AOP 代理对象生成逻辑源码分析

1. spring aop案例(POJO注入) 1.0 被代理接口 TargetInterface /** * 被代理的接口 * @author Yang ZhiWei */public interface TargetInterface { void show(); String show......

ZeroneLove
今天
36
0
聊聊dubbo-go的gracefulShutdownFilter

序 本文主要研究一下dubbo-go的gracefulShutdownFilter gracefulShutdownFilter dubbo-go-v1.4.2/filter/filter_impl/graceful_shutdown_filter.go type gracefulShutdownFilter struct {......

go4it
今天
30
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部