题目大意
有一个 (n) 个点组成的树，有 (m) 次操作，每次将 (1 o x) 的路径上每个点都加入一个颜色为 (c) 的小球。但是每个点都有大小限制，即小球个数超过一定量之后就不能再加入了。有 (q) 次查询，问操作完了之后每个点有多少种不同颜色的小球。
思路
stO llsw yyds Orz
以下皆为 llsw yyds 的思路，与本人无关。
我们首先可以整体二分出每一个点在多久会被填满，然后扫描线一波，问题就是如何判断一个子树内不同颜色的个数。这个我们可以直接容斥，就每次加入一个颜色的时候减掉与之前重复的即可。
时间复杂度 (Theta(nlog n))。
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define Int int
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
vector <int> G[MAXN];
int n,m,uni,tmpc[MAXN];
struct Mod{
int u,c;
}seq[MAXN];
int ind,tur[MAXN],ans[MAXN],lim[MAXN],dfn[MAXN],dep[MAXN],siz[MAXN],par[MAXN][21];
void dfs (int u,int fa){
dfn[u] = ++ ind,tur[ind] = u,par[u][0] = fa,dep[u] = dep[fa] + 1,siz[u] = 1;
for (Int i = 1;i <= 20;++ i) par[u][i] = par[par[u][i - 1]][i - 1];
for (Int v : G[u]) if (v ^ fa) dfs (v,u),siz[u] += siz[v];
}
int getlca (int u,int v){
if (dep[u] < dep[v]) swap (u,v);
for (Int dis = dep[u] - dep[v],i = 20;~i;-- i) if (dis >> i & 1) u = par[u][i];
if (u == v) return u;
else{
for (Int i = 20;~i;-- i) if (par[u][i] ^ par[v][i]) u = par[u][i],v = par[v][i];
return par[u][0];
}
}
struct Bit_Tree{
int sum[MAXN];
int lowbit (int x){return x & (-x);}
void modify (int x,int v){for (Int i = x;i <= n;i += lowbit (i)) sum[i] += v;}
int query (int x){int res = 0;for (Int i = x;i;i -= lowbit (i)) res += sum[i];return res;}
int query (int l,int r){return query (r) - query (l - 1);}
}Tree;
vector <int> qry[MAXN];
void Solve (vector <int> &tmp,int l,int r){
if (tmp.empty()) return ;
if (l == r){
for (Int u : tmp) qry[l].push_back (u);
return tmp.clear();
}
vector <int> lson,rson;
int mid = (l + r) >> 1;
for (Int i = l ? l : 1;i <= mid;++ i) Tree.modify (dfn[seq[i].u],1);
for (Int u : tmp){
if (Tree.query (dfn[u],dfn[u] + siz[u] - 1) < lim[u]) rson.push_back (u);
else lson.push_back (u);
}
tmp.clear();
Solve (rson,mid + 1,r);
for (Int i = l ? l : 1;i <= mid;++ i) Tree.modify (dfn[seq[i].u],-1);
Solve (lson,l,mid);
}
set <int> colS[MAXN];
void Insert (set <int> &S,int u){
auto res = S.insert (dfn[u]);
if (!res.second) return ;
Tree.modify (dfn[u],1);
auto it = res.first;int p = -1,q = -1;
if (it != S.begin()) Tree.modify (dfn[getlca (u,p = tur[*-- it])],-1),++ it;
if (++ it != S.end()) Tree.modify (dfn[getlca (u,q = tur[*it])],-1);
if (~q && ~p) Tree.modify (dfn[getlca (p,q)],1);
}
signed main(){
read (n);
for (Int i = 2,u,v;i <= n;++ i) read (u,v),G[u].push_back (v),G[v].push_back (u);
for (Int i = 1;i <= n;++ i) read (lim[i]);
read (m);
for (Int i = 1;i <= m;++ i) read (seq[i].u,seq[i].c),tmpc[i] = seq[i].c;
sort (tmpc + 1,tmpc + m + 1),uni = unique (tmpc + 1,tmpc + m + 1) - tmpc - 1;
for (Int i = 1;i <= m;++ i) seq[i].c = lower_bound (tmpc + 1,tmpc + m + 1,seq[i].c) - tmpc;
dfs (1,0);
vector <int> tmp;for (Int i = 1;i <= n;++ i) tmp.push_back (i);
Solve (tmp,0,m);
for (Int i = 1;i <= m;++ i){
Insert (colS[seq[i].c],seq[i].u);
for (Int u : qry[i]) ans[u] = Tree.query (dfn[u],dfn[u] + siz[u] - 1);
}
int q;read (q);
for (Int i = 1,x;i <= q;++ i) read (x),write (ans[x]),putchar ('
');
return 0;
}