11046: 【原1046】二哥的吊灯

题目描述

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

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];
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() {
// input tree structure
for (register int i = 0; i < n; ++i) {
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--) {