11356: 【原1356】最大孩子

题目

题目描述

author: Kainan Wang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1356

Description

现在给定一个树内所有边，树的根节点编号以及几个询问，输出被询问的节点的最大孩子的号码。如果被询问的节点没有孩子，输出-1。

Input Format

第一行：两个整数N，R，空格分开。其中N (1 <= N <= 100000)为节点数量，R为根节点的标号。

接下来N-1行：每行两个整数x和y，空格分隔。代表x节点和y节点相互连接，(0 <= x,y < N)。

第(N+1)行：一个整数Q (1 <= Q <= 100000)，代表操作数量。

接下来Q行：一个整数u。u (0 <= u < N)为被询问的节点号码。

Output Format

共Q行，每行一个整数k。

k为被询问的节点的孩子中号码最大的号码。

Input Sample

3 2
0 1
1 2
3
0
1
2

Output Sample

-1
0
1

WashSwang's solution

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int x,y,n,r,q,num=1,last[300000],to[300000],ne[300000],maxson[300000];
bool vis[300000];
void add(int u,int v){
    to[num]=v;
    ne[num]=last[u];
    last[u]=num;
    num++;
}
void find(int x){
    vis[x]=true;
    for (int i=last[x];i;i=ne[i])
        if (!vis[to[i]]){
            find(to[i]);
            maxson[x]=max(maxson[x],to[i]);
        }
}
int main() {
    memset(maxson,-1,sizeof(maxson));
    scanf("%d%d",&n,&r);
    for (int i=0;i<n-1;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    find(r);
    scanf("%d",&q);
    for (int i=0;i<q;++i)
    {
        scanf("%d",&x);
        printf("%d\n",maxson[x]);
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <vector>
#define MAX_N 100010
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
struct Node {
    int max_child_id;
    vector<int> child_id;
}tree[MAX_N];
int n, root, q;
vector<int> link_id[MAX_N];
bool vis[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
void build_tree(int x) {
    for (register int i = 0; i < link_id[x].size(); ++i)
        if (!vis[link_id[x][i]]) {// not parent
            vis[link_id[x][i]] = true;
            tree[x].child_id.push_back(link_id[x][i]);
            build_tree(link_id[x][i]);// dfs to build tree
        }
    int cur_max = -1;
    for (register int i = 0; i < tree[x].child_id.size(); ++i) {
        // max of the adjacent child
        cur_max = max(cur_max, tree[x].child_id[i]);
        // sb题目,孩子指直接相连的子节点
        // max of children of the adjacent child
        // cur_max = max(cur_max, tree[tree[x].child_id[i]].max_child_id);
    }
    tree[x].max_child_id = cur_max;
}
int main() {
    n = read(), root = read();
    for (register int i = 1; i < n; ++i) {
        int x = read(), y = read();
        link_id[x].push_back(y);
        link_id[y].push_back(x);
    }
    vis[root] = true;
    build_tree(root);
    q = read();
    while (q--) {
        int x = read();
        printf("%d\n", tree[x].max_child_id);
    }
    return 0;
}