codeforces 375D . Tree and Queries 启发式合并 || dfs序+莫队

题目链接

一个n个节点的树， 每一个节点有一个颜色， 1是根节点。 m个询问， 每个询问给出u， k。 输出u的子树中出现次数大于等于k的颜色的数量。

启发式合并， 先将输入读进来， 然后dfs完一个节点就处理跟它有关的询问。

感觉不是很难， 然而.....WA了n次最后还是看的别人的代码

 #include <iostream>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <map>

 #include <set>

 #include <string>

 #include <queue>

 #include <stack>

 #include <bitset>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, n, a) for(int i = a; i<n; i++)

 #define fi first

 #define se second

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 const int maxn = 1e5+;

 int head[maxn*], num, id[maxn], val[maxn], ans[maxn];

 struct node

 {

     int to, nextt, w;

 }e[maxn*];

 void add(int u, int v) {

     e[num].to = v, e[num].nextt = head[u], head[u] = num++;

 }

 void init() {

     num = ;

     mem1(head);

 }

 struct Node

 {

     map <int, int> mp;

     vector <int> ve;

     int sz = ;

     void add(int x) {

         mp[x]++;

         while(mp[x]>=ve.size()) {

             ve.push_back();

         }

         ve[mp[x]]++;

         sz++;

     }

 }st[maxn];

 vector <pll> v[maxn];

 void combine(int& x, int& y) {

     if(st[x].sz<st[y].sz)

         swap(x, y);

     for(auto it = st[y].mp.begin(); it!=st[y].mp.end(); it++) {

         for(int i = ; i<it->second; i++) {

             st[x].add(it->first);

         }

     }

 }

 void dfs(int u, int fa) {

     st[u].add(val[u]);

     for(int i = head[u]; ~i; i = e[i].nextt) {

         int vx = e[i].to;

         if(vx == fa)

             continue;

         dfs(vx, u);

         combine(id[u], id[vx]);

     }

     for(int i = ; i<v[u].size(); i++) {

         int x = v[u][i].fi, y = v[u][i].se;

         if(x>=st[id[u]].ve.size())

             continue;

         ans[y] = st[id[u]].ve[x];

     }

 }

 int main()

 {

     int n, m, x, y;

     cin>>n>>m;

     init();

     for(int i = ; i<=n; i++) {

         scanf("%d", &val[i]);

         id[i] = i;

     }

     for(int i = ; i<n-; i++) {

         scanf("%d%d", &x, &y);

         add(x, y);

         add(y, x);

     }

     for(int i = ; i<m; ++i) {

         scanf("%d%d", &x, &y);

         v[x].pb(mk(y, i));

     }

     dfs(, );

     for(int i = ; i<m; i++)

         cout<<ans[i]<<endl;

     return ;

 }