锐客网

  1. 首页 > it技术 > >

题解|[Codeforces375D]Tree and Queries（dsu on the tree+bit）

题解Thebittreeondsu

题目描述 传送门
题意：一棵树，每个点有一个颜色，每一次询问以x为根的子树中至少出现k次的颜色有多少种
题解 【题解|[Codeforces375D]Tree and Queries（dsu on the tree+bit）】dsu on the tree…
记每一个颜色出现了多少次，再记出现多少次的颜色有多少个
因为是至少出现k次，挂一个bit就行了
注意bit更新的时候每一次都到最大值
代码

#include #include #include #include #include using namespace std; #define N 200005 #define inf 200000int n,m,Son; int tot,point[N],nxt[N*2],v[N*2]; int cq,pq[N],nxtq[N],vq[N],idq[N]; int size[N],son[N],c[N],cnt[N],C[N],ans[N]; void add(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void addq(int x,int y,int z) { ++cq; nxtq[cq]=pq[x]; pq[x]=cq; vq[cq]=y; idq[cq]=z; } void getson(int x,int fa) { size[x]=1; for (int i=point[x]; i; i=nxt[i]) if (v[i]!=fa) { getson(v[i],x); size[x]+=size[v[i]]; if (size[v[i]]>size[son[x]]) son[x]=v[i]; } } void change(int loc,int val) { for (int i=loc; i<=inf; i+=i&-i) C[i]+=val; } int query(int loc) { int ans=0; for (int i=loc; i>=1; i-=i&-i) ans+=C[i]; return ans; } void calc(int x,int fa,int opt) { if (cnt[c[x]]) change(cnt[c[x]],-1); cnt[c[x]]+=opt; if (cnt[c[x]]) change(cnt[c[x]],1); for (int i=point[x]; i; i=nxt[i]) if (v[i]!=fa&&v[i]!=Son) calc(v[i],x,opt); } void dfs(int x,int fa,int k) { for (int i=point[x]; i; i=nxt[i]) if (v[i]!=fa&&v[i]!=son[x]) dfs(v[i],x,0); if (son[x]) dfs(son[x],x,1),Son=son[x]; calc(x,fa,1); Son=0; for (int i=pq[x]; i; i=nxtq[i]) { int x=query(inf); int y=query(vq[i]-1); ans[idq[i]]=x-y; } if (!k) calc(x,fa,-1); } int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; ++i) scanf("%d",&c[i]); for (int i=1; i

    推荐阅读


    上一篇：被一根红条子搅乱的心思

    下一篇：专车打到了前男友的车...