盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU5156 Harry and Christmas tree(dfs序+查询区间内有多少个数)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5156

题意

有一颗树,每个节点上有一些颜色的礼物,现在问以每个节点为根的子树有多少种不同的颜色。

思路

先把每个节点相同的颜色去除,然后按照dfs序得到一个关于颜色的序列。问题就转化为查询若干个区间内有多少种不同的颜色。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 50000 + 10;
const int M = 500000 + 10;
vector<int> g[N], gift[N];
int st[N], ed[N], pos[N], ans[N], mp[2 * N], seq[M], s[M], nxt[M];
int tot, n, m;
bool cmp1(int a, int b) { ///按左区间从小到大排
return st[a] < st[b];
}
bool cmp(int a, int b) { ///按有区间从小到大排
return ed[a] < ed[b];
}
int lowbit(int x) {
return x & -x;
}
void add(int p, int v) {
while(p <= tot) {
s[p] += v;
p += lowbit(p);
}
}
int sum(int p) {
int res = 0;
while(p > 0) {
res += s[p];
p -= lowbit(p);
}
return res;
}
void dfs(int u, int fa) {
st[u] = tot + 1;
for (int i = 0; i < gift[u].size(); i++) seq[++tot] = gift[u][i];
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v != fa) dfs(v, u);
}
ed[u] = tot;
}
void init() {
tot = 0;
for (int i = 1; i <= n; i++) {
g[i].clear();
gift[i].clear();
pos[i] = i;
}
}
int main () {
while(~scanf("%d%d", &n, &m)) {
init();
int u, v;
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
int mx = 0;
while(m--) {
scanf("%d%d", &u, &v);
if (find(gift[u].begin(), gift[u].end(), v) == gift[u].end()) gift[u].pb(v);
mx = max(mx, v);
}
dfs(1, -1);
memset(s, 0, sizeof(int) * (tot + 5));
memset(mp, 0, sizeof(int) * (mx + 5));
///按右区间从小到大排
sort(pos + 1, pos + n + 1, cmp);
for(int i = 1; i <= tot; i++) {
if(!mp[seq[i]]) {
add(i, 1);
mp[seq[i]] = i; ///如果是第一次出现, mp[seq[i]]记录为当前位置
}
}
int right = 1;
for(int i = 1; i <= n; i++) {
int now = pos[i];
while(right <= ed[now]) {
if(mp[seq[right]] != right) { ///如果不是第一次出现
add(mp[seq[right]], -1); ///减去前一次出现的
add(right, 1);
mp[seq[right]] = right; ///重新定义这个数最近一次出现位置
}
right++;
}
ans[now] = sum(ed[now]) - sum(st[now] - 1);
}
/*
///按左区间从小到大排
for (int i = 1; i <= tot; i++) {
if (!mp[seq[i]]) {
mp[seq[i]] = i;
add(i, 1);
}
}
memset(mp, 0, sizeof(int) * (mx + 5));
for (int i = tot; i >= 1; i--) {
if (!mp[seq[i]]) nxt[i] = tot + 1;
else nxt[i] = mp[seq[i]];
mp[seq[i]] = i;
}
sort(pos + 1, pos + n + 1, cmp1);
int t = 1;
for (int i = 1; i <= n; i++) {
int now = pos[i];
while(t <= tot && t < st[now]) {
add(nxt[t++], 1);
}
//cout<<now<<" "<<st[now]<<" "<<ed[now]<<endl;
ans[now] = sum(ed[now]) - sum(st[now] - 1);
}
*/
for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
}
return 0;
}