Parent and son

Give you a tree with N vertices and N‐ 1 edges, and then ask you Q queries on “which vertex is Y‘s son that has the smallest number and which vertex is Y’s descendants that has the smallest number if we choose X as the root of the entire tree?”

InputThe first line of input is an integer T (T<=10) means the case number. 
The first line of each test case contains N(2 ≤ N ≤ 100,000) and Q(1 ≤ Q ≤ 100,000). 
Each of the following N ‐ 1 lines of the test case contains two integers a(1 ≤ a ≤ N) and b(1 ≤ b ≤ N) indicating an edge between a and b. 
Each of the following Q lines of the test case contains two integers X(1 ≤ X ≤ N) and Y(1 ≤ Y ≤ N, Y ≠ X) indicating an query. 
OutputFor each query, output the Y‘s son which has the smallest number and Y‘s descendant that has the smallest number if X is the root of the entire tree. If Y has no sons then output “no answers!”. There is an empty line after each case.Sample Input

1
7 3
1 2
1 5
2 3
2 4
5 6
5 7
1 2
5 3
3 2

Sample Output

3 3
no answers!
1 1
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<memory>
#include<bitset>
#include<string>
#include<functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define MAXN 100006
#define INF 0x3f3f3f3f

struct edge
{
    int to, next;
}E[MAXN*2];
int tot, sz, head[MAXN], L[MAXN], R[MAXN], s[MAXN], fa[MAXN];
void init()
{
    tot = 0;
    sz = 0;
    memset(head, -1, sizeof(head));
    memset(s, 0, sizeof(s));
}
void addedge(int f, int t)
{
    E[tot].to = t;
    E[tot].next = head[f];
    head[f] = tot++;
}
struct node
{
    int min1, min2, id1, id2;
}sn[MAXN],st[MAXN];

void getmin(node& tmp, int num, int v)
{
    if (tmp.min1 > num)
    {
        tmp.min2 = tmp.min1, tmp.id2 = tmp.id1;
        tmp.min1 = num, tmp.id1 = v;
    }
    else if (tmp.min2 > num)
    {
        tmp.min2 = num, tmp.id2 = v;
    }
}

void dfs(int u, int pre)
{
    L[u] = ++sz;
    sn[u].min1 = sn[u].min2 = st[u].min1 = st[u].min2 = INF;
    for (int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].to;
        if (v == pre) continue;
        dfs(v, u);
        fa[v] = u;
        getmin(sn[u], v, v);
        getmin(st[u], min(st[v].min1, v), v);
    }
    R[u] = sz;
}
int main()
{
    int T, n, u, v, q, X, Y;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &q);
        init();
        for (int i = 0; i < n - 1; i++)
        {
            scanf("%d%d", &u, &v);
            s[u]++;
            s[v]++;
            addedge(u, v);
            addedge(v, u);
        }
        sz = 0;
        fa[1] = INF;
        dfs(1, 0);
        while (q--)
        {
            scanf("%d%d", &X, &Y);
            if (s[Y] == 1)
                printf("no answers!\n");
            else if (L[X]<L[Y] || R[X]>R[Y])
                printf("%d %d\n", sn[Y].min1, st[Y].min1);
            else
            {
                int ans = 1;
                if (Y == 1)
                {
                    if (L[st[Y].id1] <= L[X] && R[st[Y].id1] >= R[X])
                    {
                        ans = st[Y].min2;
                    }
                    else
                        ans = st[Y].min1;
                }
                if (L[sn[Y].id1] <= L[X] && R[sn[Y].id1] >= R[X])
                {
                    printf("%d %d\n", min(fa[Y], sn[Y].min2), ans);
                }
                else
                    printf("%d %d\n", min(fa[Y], sn[Y].min1), ans);
            }
        }
        printf("\n");
    }
}
时间: 08-15

Parent and son的相关文章

HDU 4008 Parent and son LCA+树形dp

题意: 给定case数 给定n个点的树,m个询问 下面n-1行给出树边 m个询问 x y 问:以x为根,y子树下 y的最小点标的儿子节点 和子孙节点 思路: 用son[u][0] 表示u的最小儿子 son[u][2] 表示u的次小儿子 son[u][1] 表示u的最小子孙 若lca(x,y)  !=y  则就是上述的答案 若lca(x,y) == y 1.y != 1 那么最小儿子就是除了x外的节点,且此时father[y] 也是y的儿子节点, 而最小的子孙节点就是1 2.y==1 那么特殊处理

parent,son深刻理解this,super关键字

核心点: super关键字,表示调用的是父类对象. this关键字,表示调用的是当前运行类对象. 那么如果在父类中,使用了关键字,this,此时的this指的是什么呢? 看下面的例子,再加深理解核心店的第二句话就ok了. parent类: package com.ghsy.thissuper; public class Parent { public void init(){ System.out.println(this.getClass()); //获得当前运行类 System.out.pr

HDU4008 Parent and son(树形DP LCA)

先记录以1为根时每个节点子树儿子节点的最大与次小值,询问x, y时,先判断x在不在y的子树范围内,若不在,结果为y的儿子结点,后继的最小值. 若x在y的子树范围内,若y儿子最小值是x的前驱,从次小值与父亲节点转移,否则从最小值与父亲节点转移. #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<al

HDU 4008 Parent and son

树形DP+LCA+思路.这题可真是有点难度......所以准备详细写一下题解. 题意:给一颗无根树,有Q次询问,每次询问指定一个根节点X,然后让你计算Y节点的儿子和子孙中,编号最小的节点是多少. 我们先以1为根节点进行一次树形DP,记录下每个节点的儿子和子孙中,编号最小的节点是多少. 首先很容易想到一种情况:就是X和Y的最近公共祖先不是Y,这个时候,结果和以1为根节点建树是一模一样的,因为把X提到最上面去,不会影响到Y的子树的情况. 剩余的情况就是X和Y的最近公共祖先等于Y(这种情况就是X在Y的

HDU 4008 Parent and son (数据结构)

 题意: 一颗结点数为(100,000)的树,最多询问100,000次.每次询问对两个结点X,Y,以X为根,Y的最小标号的孩子,Y的最小标号的后代. 思路:如果dfs n次那么时间复杂度无法承受,我们考虑只dfs一次. 以1为根节点dfs一次,记录每个点的最小和次小儿子值和最小后代值,考虑询问x, y,如果x不是y的子孙节点,那么答案就是y的最小儿子值和最小后代值. 如果x是y的子孙节点,又分为两种情况, 首先考虑y不为1的时候,那么y的最小后代值一定为1,如果x所在子树的y的儿子节点的值为

16种方法实现水平居中垂直居中

时间:2017-04-24 00:09:58      阅读:29      评论:0      收藏:0      [点我收藏+] 转载下别人收集的定位方法,写的比较详细,比如子元素定位要先考虑父元素的是行内元素还是块内元素,transform灵活运用等等. 水平居中 1) 若是行内元素, 给其父元素设置 text-align:center,即可实现行内元素水平居中. 2) 若是块级元素, 该元素设置 margin:0 auto即可. 3) 若子元素包含 float:left 属性, 为了让子

《深入理解Java虚拟机》:类加载的过程

<深入理解Java虚拟机>:类加载的过程 类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载.验证.准备.解析.初始化.使用和卸载七个阶段.其中类加载的过程包括了加载.验证.准备.解析.初始化五个阶段. 下面详细讲述类加载过程中每个阶段所做的工作. 加载 加载时类加载过程的第一个阶段,在加载阶段,虚拟机需要完成以下三件事情: 1.通过一个类的全限定名来获取其定义的二进制字节流. 2.将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构. 3.在Java堆中生成一

[ACM] hihocoder 1062 最近公共祖先&#183;一 (一般做法)

描述 小Ho最近发现了一个神奇的网站!虽然还不够像58同城那样神奇,但这个网站仍然让小Ho乐在其中,但这是为什么呢? "为什么呢?"小Hi如是问道,在他的观察中小Ho已经沉迷这个网站一周之久了,甚至连他心爱的树玩具都弃置一边. "嘿嘿,小Hi,你快过来看!"小Ho招呼道. "你看,在这个对话框里输入我的名字,在另一个对话框里,输入你的名字,再点这个查询按钮,就可以查出来--什么!我们居然有同一个祖祖祖祖祖爷爷?" "诶,真是诶--这个网

Boost智能指针-基础篇

简介 内存管理一直是 C++ 一个比较繁琐的问题,而智能指针却可以很好的解决这个问题,在初始化时就已经预定了删除,排解了后顾之忧.1998年修订的第一版C++标准只提供了一种智能指针:std::auto_ptr(现以废弃),它基本上就像是个普通的指针:通过地址来访问一个动态分配的对象.std::auto_ptr之所以被看作是智能指针,是因为它会在析构的时候调用delete操作符来自动释放所包含的对象.当然这要求在初始化的时候,传给它一个由new操作符返回的对象的地址.既然std::auto_pt