传送门
前70pts巨水,
不过没有数据范围就可以为所欲为吗。。。
颜色是负数是几个意思。。。
以后见到这类不给数据范围的题先离散化
发现每个节点的操作都会向上影响到根节点
貌似可以启发式合并一路维护上去
考虑如何处理这个每个节点只能放 \(k\) 个球的限制
在每个节点维护一棵splay,以时间为下标,存这个时刻放入的小球颜色及是否对答案产生贡献
(每种颜色第一次出现的小球贡献为1,其余为0)
然后每个节点再开一个map记录这个节点每种颜色第一次出现的时间就好
每次插入如果比这个时间早就找到原来的点把贡献改成0
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 100010 #define ll long long #define fir first #define sec second #define make make_pair //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n, m, q; int head[N], size, k[N], uni[N], usize, qx[N], qc[N], ans[N], siz2[N], msiz[N], mson[N]; struct edge{int to, next;}e[N<<1]; inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;} int tot, rab[N<<3], rtop; int siz[N<<3], col[N<<3], tim[N<<3], val[N<<3], sum[N<<3], son[N<<3][2], fa[N<<3]; #define siz(p) siz[p] #define col(p) col[p] #define tim(p) tim[p] #define val(p) val[p] #define sum(p) sum[p] #define son(a, b) son[a][b] #define fa(p) fa[p] #define loc(p) (son(fa(p), 1)==p) #define tran(a, x) son(a, (x)>tim(a)) #define pushup(p) sum(p)=sum(son(p, 0))+sum(son(p, 1))+val(p);\ siz(p)=siz(son(p, 0))+siz(son(p, 1))+1 struct Splay{ int rot; unordered_map< int, pair<int, int> > mp; Splay():rot(0){ins(-INF, -1, 0); ins(INF, -1, 0);} void ror(int x) { int y=fa(x), z=fa(y), k=loc(x); son(z, loc(y))=x; fa(x)=z; son(y, k)=son(x, k^1); fa(son(x, k^1))=y; son(x, k^1)=y; fa(y)=x; pushup(y); pushup(x); } void splay(int x, int pos) { int y, z; while (fa(x)!=pos) { y=fa(x), z=fa(y); if (z!=pos) loc(x)^loc(y)?ror(x):ror(y); ror(x); } if (!pos) rot=x; } void ins(int t, int c, int d) { //if (c!=-1) cout<<"ins: "<<t<<' '<<c<<' '<<d<<endl; if (d && mp.find(c)!=mp.end()) { pair<int, int> tem=mp[c]; if (tem.fir<t) d=0; else { val(tem.sec)=0; splay(tem.sec, 0); } } int u=rot, f=0; while (u) f=u, u=tran(u, t); //u=(rtop?rab[rtop--]:++tot); u=++tot; siz(u)=1; col(u)=c; tim(u)=t; val(u)=sum(u)=d; if (f) tran(f, t)=u; if (d) mp[c]=make(t, u); son(u, 0)=son(u, 1)=0; fa(u)=f; splay(u, 0); //if (c!=-1) cout<<"u: "<<u<<' '<<val(u)<<' '<<sum(u)<<endl; } void find(int x) { int u=rot; while (u&&tran(u, x)) u=tran(u, x); splay(u, 0); } int rk(int x) { //cout<<"rk: "<<x<<' '<<siz(rot)<<endl; int u=rot, v; if (x>=siz(u)) return sum(u); while (1) { v=son(u, 0); if (x<=siz(v)) u=v; else if (x>siz(v)+1) u=son(u, 1), x-=siz(v)+1; else {splay(u, 0); return sum(son(u, 0));} } } void merge(int u, Splay& a) { //cout<<"merge "<<u<<' '<<tim(u)<<' '<<col(u)<<endl; if (son(u, 0)) merge(son(u, 0), a); if (son(u, 1)) merge(son(u, 1), a); if (col(u)!=-1) a.ins(tim(u), col(u), 1); rab[++rtop]=u; } }rot[N]; void dfs(int u, int fa) { //cout<<"dfs "<<u<<' '<<fa<<endl; msiz[u]=siz2[u]=siz(rot[u].rot)-2; mson[u]=u; for (int i=head[u],v; ~i; i=e[i].next) { v = e[i].to; if (v==fa) continue; dfs(v, u); siz2[u]+=siz(rot[v].rot)-2; if (siz(rot[v].rot)-2>msiz[u]) msiz[u]=siz(rot[v].rot)-2, mson[u]=v; } //cout<<"mson: "<<mson[u]<<endl; swap(rot[u], rot[mson[u]]); //cout<<"swap "<<u<<endl; for (int i=head[u],v; ~i; i=e[i].next) { v = e[i].to; if (v==fa) continue; //cout<<"goto merge "<<u<<' '<<v<<endl; rot[v].merge(rot[v].rot, rot[u]); //cout<<"return merge"<<endl; } ans[u]=rot[u].rk(k[u]+2); //cout<<"return "<<u<<endl; } signed main() { memset(head, -1, sizeof(head)); n=read(); for (int i=1,u,v; i<n; ++i) { u=read(); v=read(); add(u, v); add(v, u); } for (int i=1; i<=n; ++i) k[i]=read(); m=read(); for (int i=1; i<=m; ++i) qx[i]=read(), qc[i]=read(), uni[i]=qc[i]; //cout<<"qc: "; for (int i=1; i<=m; ++i) cout<<qc[i]<<' '; cout<<endl; sort(uni+1, uni+m+1); usize=unique(uni+1, uni+m+1)-uni-1; for (int i=1; i<=m; ++i) qc[i]=lower_bound(uni+1, uni+usize+1, qc[i])-uni; //cout<<"qc: "; for (int i=1; i<=m; ++i) cout<<qc[i]<<' '; cout<<endl; for (int i=1; i<=m; ++i) rot[qx[i]].ins(i, qc[i], 1); //, cout<<"qins"<<endl; dfs(1, 0); q=read(); for (int i=1; i<=q; ++i) printf("%d\n", ans[read()]); return 0; }