# C

user_8384735
c_cpp
2 years ago
1.5 kB
4
Indexable
Never
```// subtreesize.cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e8 + 5;
struct node{
int size, tag;
bool v;
node *right, *left;
node(int x = 1) :tag(x), size(1), right(0), left(0), v(1){}
};
int root = 1, cnt = 1;
vector<node*> G(N);
int in[N];
int m, n, maxi;
void bfs(){
queue<node*> q;
q.push(G[root]);
while (!q.empty()){
auto u = q.front(); q.pop();
cout << u->tag << " " << u->size << endl;
if (u->left) q.push(u->left);
if (u->right) q.push(u->right);

}
}
int dfs(node *u){
if (u->right) u->size += dfs(u->right);
if (u->left) u->size += dfs(u->left);
return u->size;
}

void input(){
G[root] = new node();
for (int i = 0; i < m; i++)
cin >> in[i];
sort(in, in + m);
for (int i = 1; i < m; i++){
G[in[i]] = new node(in[i]);
if (in[i] % 2){
G[in[i] / 2]->right = G[in[i]];
}else G[in[i] / 2]->left = G[in[i]];
}
}
int main(){
cin >> m >> n;
input();
dfs(G[root]);
bfs();
}
/*

Input:
第一行有兩個整數m,n. n 是此樹的最大深度 1 <= n <= 333;
m 為接下來有 m 個整數來表示有此節點 m <= 1e5
Oouput:
輸出子數 >= 1 的節點 同行輸出節點的子樹數量
Sample:
Input:
6 5          1
1         2     3
2		 4 5      7
3
4
5
7
Output:
1 6
2 3
3 2
4 1
5 1
7 1
*/```