Skip to content

11046: 【原1046】二哥的吊灯

题目

题目描述

author: oldherl 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1046

Description

二哥新买了一顶二叉树形状的吊灯,每个结点处都有一个白色的灯泡。但是二哥的女友觉得都是白色的灯不好看,就让二哥把部分灯泡涂成红色。

涂色的方法是这样的:二哥的女友指着一个灯泡(结点),并报出一个数字X,让二哥把这棵以该结点为根的子树(假设有Y个节点)中序遍历一下,把遍历序列中的第(X%Y + 1)个灯泡涂成红色。

这样操作了若干次以后,二哥的女友又提出了若干个问题:以某结点为根的子树中一共有多少个被涂成红色的灯泡呢?

Input Format

第 1 行:三个整数 N,P,Q 分别表示吊灯的灯泡数、涂色的次数以及询问的个数

以下 N 行:每行三个整数 x, Lx, Rx 描述一个节点。分别为该结点的编号、它的左儿子的编号、它的右儿子的编号。Lx或者Rx为0表示该儿子不存在。保证节点编号都是1到N的整数且没有重复

以下 P 行:每行两个整数 t, x 表示一个涂色操作:中序遍历以t节点为根的子树并进行如上所述的涂色操作

最后 Q 行:每行一个整数 w 表示一个询问:以w结点为根的子树中一共有多少个被涂成红色的灯泡?

Output Format

共Q行,对于每一个询问,输出相应的答案。

Hint

对70%的数据,N,P,Q <= 2011

对100%的数据,3 <= N,P,Q <= 100000。

题目中出现的所有数均为不超过 100000 的非负整数。

样例说明

被涂红的灯泡依次为 3,4,3 号。

Sample Input

5 3 3
2 3 4
3 1 5
4 0 0
1 0 0
5 0 0
2 1
4 1
3 4
1
2
3

Sample Output

0
2
1

FineArtz's solution

/* 二哥的吊灯 */
#include <iostream>
using namespace std;

class Node{
public:
    int l = 0, r = 0, total = 0, red = 0;
    bool isRed = false;
};

Node a[100005];
int pos[100005];
bool b[100005];
int n, p, q;

int count1(int x){
    int r = 0;
    if (a[x].l != 0)
        r += count1(pos[a[x].l]);
    if (a[x].r != 0)
        r += count1(pos[a[x].r]);
    a[x].total = r + 1;
    return a[x].total;
}

void dye(int t, int x){
    int y = a[pos[a[t].l]].total;
    if (y == x - 1){
        a[t].isRed = true;
        return;
    }
    else if (y < x - 1){
        dye(pos[a[t].r], x - y - 1);
    }
    else{
        dye(pos[a[t].l], x);
    }
}

int count2(int x){
    int r = 0;
    if (a[x].l != 0)
        r += count2(pos[a[x].l]);
    if (a[x].r != 0)
        r += count2(pos[a[x].r]);
    if (a[x].isRed)
        ++r;
    a[x].red = r;
    return a[x].red;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; ++i){
        int x, lx, rx;
        cin >> x >> lx >> rx;
        a[i].l = lx;
        a[i].r = rx;
        b[lx] = true;
        b[rx] = true;
        pos[x] = i;
    }
    int root = 0;
    for (int i = 1; i <= n; ++i){
        if (!b[i]){
            root = i;
            break;
        }
    }
    count1(pos[root]);
    while (p--){
        int t, x;
        cin >> t >> x;
        dye(pos[t], x % a[pos[t]].total + 1);
    }
    count2(pos[root]);
    while (q--){
        int x;
        cin >> x;
        cout << a[pos[x]].red << '\n';
    }
    return 0;
}

ligongzzz's solution

#include <iostream>
using namespace std;

class node {
public:
    int lchild = 0, rchild = 0;
    int num = 1;
    int red_num = 0;
    bool is_red = false;
    int parent = 0;
};

node node_list[100009];

int dfs(int root) {
    if (node_list[root].lchild)
        node_list[root].num += dfs(node_list[root].lchild);
    if (node_list[root].rchild)
        node_list[root].num += dfs(node_list[root].rchild);
    return node_list[root].num;
}

void paint_red(int root,int pos) {
    pos = pos % node_list[root].num;
    int this_pos = node_list[root].lchild ? node_list[node_list[root].lchild].num : 0;
    if (pos == this_pos) {
        if (!node_list[root].is_red) {
            node_list[root].is_red = true;
            for (auto p = root; p; p = node_list[p].parent)
                ++node_list[p].red_num;
        }
        return;
    }
    else if (pos < this_pos) {
        paint_red(node_list[root].lchild, pos);
    }
    else {
        paint_red(node_list[root].rchild, pos - this_pos - 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, p, q;
    cin >> n >> p >> q;

    for (int i = 0; i < n; ++i) {
        int x, l, r;
        cin >> x >> l >> r;

        node_list[x].lchild = l;
        node_list[x].rchild = r;
        if (l)
            node_list[l].parent = x;
        if (r)
            node_list[r].parent = x;
    }

    int root = 0;
    for(int i=1;i<=n;++i)
        if (node_list[i].parent == 0) {
            root = i;
            break;
        }

    dfs(root);

    for (int i = 0; i < p; ++i) {
        int t, x;
        cin >> t >> x;
        paint_red(t, x);
    }

    for (int i = 0; i < q; ++i) {
        int w;
        cin >> w;
        cout << node_list[w].red_num << "\n";
    }

    return 0;
}

yyong119's solution

#include <cstdio>
#define MAX_N 100010
using namespace std;
int n, p, q, root;
struct Node {
    int par, ls, rs, size, red, color;// color == 1 means red
} tree[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_size(int x) {
    if (!tree[x].ls && !tree[x].rs) {
        tree[x].size = 1;
        return;
    }
    if (tree[x].ls) build_tree_size(tree[x].ls);
    if (tree[x].rs) build_tree_size(tree[x].rs);
    tree[x].size = tree[tree[x].ls].size + tree[tree[x].rs].size + 1;
}
void push_up(int x) {
    ++tree[x].red;
    if (tree[x].par) push_up(tree[x].par);
}
void dye(int x, int num) {
    int l_size = tree[tree[x].ls].size;
    // just node x
    if (num == l_size + 1) {
        // haven't been dyed to red
        if (!tree[x].color) {
            tree[x].color = 1;
            // red size for each parent of x(including x) increase 1
            push_up(x);
        }
        return;
    }
    // at left part
    if (num <= l_size) dye(tree[x].ls, num);
    // at right part
    if (num > l_size + 1) dye(tree[x].rs, num - l_size - 1);
}
int main() {
    n = read(), p = read(), q = read();
    // input tree structure
    for (register int i = 0; i < n; ++i) {
        int par = read(), ls = read(), rs = read();
        tree[par].ls = ls; tree[par].rs = rs;
        tree[ls].par = par; tree[rs].par = par;
    }
    // find root
    for (register int i = 1; i <= n; ++i)
        if (!tree[i].par) {
            root = i; break;
        }
    // get size of each node
    build_tree_size(root);
    // for (int x = 1; x <= n; ++x)
    //     printf("%d ", tree[x].size);
    // printf("\n");
    // dye red color
    while (p--) {
        int x = read(), t = read();
        dye(x, t % tree[x].size + 1);
    }
    // query number of red color
    while (q--) {
        int x = read();
        printf("%d\n", tree[x].red);
    }
    return 0;
}