题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=5156
题意 :
给一颗编号为1-n的以1为根的树, 已知有m个颜色的礼物分布在某些节点上(同一节点可以有多个),
问 : 对于编号从1-n的节点, 每一个节点对应子树上有多少颜色不同的礼物.
思路 :
一开始的想法是DFS记录节点序列, 再开vector记录每个节点上挂的礼物(同一节点上对颜色去重), 用树状数组统计一个区间内不同颜色的种类
但是由于记录位置的数组同样要开到二维, 超过了限制, 于是也开成vector, 果断超时
后来还是看discuss里边sxbk同学的代码才知道更好的解法
DFS记录序列不是节点序列, 而是将所有节点的全部颜色(已去重)都记录在序列内, 这样位置记录的数组可以只用一维
这道题收获挺大的, 对DFS序的思想理解深入了, 同时学习了 统计一个区间内有多少不同的数 这个问题的解法
题目代码 :
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> using namespace std; const int MAXN = 5e4+;
const int MAXM = 5e5+; vector<int> edge[MAXN];
vector<int> gift[MAXN];
int seq[*MAXM];
int st[MAXN];
int ed[MAXN];
int s[*MAXM];
int mp[*MAXM];
int ans[MAXN];
int pos[MAXN];
int cnt, n, m; void Dfs(int u, int fa)
{
st[u] = cnt + ;
int num = gift[u].size();
for(int i = ; i < num; i++) {
seq[++cnt] = gift[u][i];
}
int len = edge[u].size();
for(int i = ; i < len; i++) {
int v = edge[u][i];
if(v != fa) Dfs(v, u);
}
ed[u] = cnt;
} int Lowbit(int x)
{
return x & (-x);
} void Add(int x, int val)
{
for(int i = x; i <= cnt; i += Lowbit(i)) {
s[i] += val;
}
} int Sum(int x)
{
int res = ;
for(int i = x; i > ; i -= Lowbit(i)) {
res += s[i];
}
return res;
} bool cmp(int a, int b)
{
return ed[a] < ed[b];
} void Init()
{
for(int i = ; i <= n; i++) {
edge[i].clear();
gift[i].clear();
}
for(int i = ; i <= n; i++) {
pos[i] = i;
}
memset(s, , sizeof(s));
memset(mp, , sizeof(mp));
} int main()
{
int u, v; while(scanf("%d %d", &n, &m) != EOF) {
Init();
for(int i = ; i < n-; i++) {
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
while(m--) {
scanf("%d %d", &u, &v);
if(find(gift[u].begin(), gift[u].end(), v) == gift[u].end()) {
gift[u].push_back(v);
}
}
cnt = ;
Dfs(, -);
sort(pos+, pos++n, cmp);
for(int i = ; i <= cnt; i++) {
if(mp[seq[i]] == ) {
Add(i, );
mp[seq[i]] = i; //如果是第一次出现, mp[seq[i]]记录为当前位置
}
}
int right = ;
for(int i = ; i <= n; i++) {
int now = pos[i];
while(right <= ed[now]) {
if(mp[seq[right]] != right) { //如果不是第一次出现
Add(mp[seq[right]], -); //减去前一次出现的
Add(right, );
mp[seq[right]] = right; //重新定义这个数最近一次出现位置
}
right++;
}
ans[now] = Sum(ed[now]) - Sum(st[now] - );
}
printf("%d", ans[]);
for(int i = ; i <= n; i++) {
printf(" %d", ans[i]);
}
printf("\n");
} return ;
}
另外第一次学习到 统计一个区间内有多少不同的数 这个问题的解法
基本思路是树状数组, 但是有重复的数, 要保证在一个区间内只更新过一次
所做的处理是用先遍历记录数字的数组a, 用数-位置数组 mp[a[i]] 来记录每个数第一次出现的位置并该点更新
这个操作对应的代码
for(int i = ; i <= n; i++) {
if(mp[a[i]] == ) { //如果是第一次出现, 记录第一次出现位置并更新
Add(i, );
mp[a[i]] = i;
}
}
记录左右查询, 每个查询按区间右端点R[i]从小到大排序
设一个扫描线k, 它的目的保证R[i]之前所有不同的点只更新过一次, 并且是在离R[i]最近的那个点更新
如此便可以写出这样一段代码
for(int i = ; i <= query_num; i++) {
while(k <= R[i]) {
if(mp[a[i]] != k) { //如果不是最新次出现
Add(mp[a[k]], -); //将上一次出现的更新-1
Add(k, ); //将这个位置新出现的更新1
mp[a[k]] = k; //更新这个数最近一次的位置
}
k++;
}
ans[i] = Sum(ed[i]) - Sum(st[i] - );
}
恩, 就是这样...