首页 > 代码库 > CSU 1811 Tree Intersection
CSU 1811 Tree Intersection
莫队算法，$dfs$序。
题目要求计算将每一条边删除之后分成的两棵树的颜色的交集中元素个数。
例如删除$u->v$，我们只需知道以$v$为$root$的子树中有多少种不同的颜色（记为$qq$），有多少种颜色达到了最多数量（记为$pp$），那么以$v$为$root$的子树与另一棵树的颜色交集中元素个数为$qq-pp$。
因为是计算子树上的量，所以可以将树转换成序列，每一个子树对应了序列中一段区间，具体计算只要用莫队算法分块就可以无脑的计算了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const int maxn=200010;struct Edge { int u,v,nx; bool f; }e[2*maxn];int h[maxn],sz,w[maxn],cnt[maxn],pos[maxn],g[maxn];int n,a[2*maxn],L[2*maxn],R[2*maxn];struct Q { int L,R,id; }q[maxn];int Ans[maxn],pp,qq;void add(int u,int v){ e[sz].u=u; e[sz].v=v; e[sz].nx=h[u]; e[sz].f=0; h[u]=sz++;}void dfs(int x,int fa){ sz++; a[sz]=w[x]; L[x]=sz; for(int i=h[x];i!=-1;i=e[i].nx) { if(e[i].v==fa) continue; e[i].f=1; dfs(e[i].v,x); } sz++; a[sz]=w[x]; R[x]=sz;}bool cmp(Q a,Q b) { if (pos[a.L]==pos[b.L]) return a.R<b.R; return a.L<b.L; }void op1(int x) { if(cnt[a[x]]-g[a[x]]==1) pp--; if(g[a[x]]==0) qq--; }void op2(int x) { if(g[a[x]]==cnt[a[x]]) pp++; if(g[a[x]]==1) qq++; }int main(){ while(~scanf("%d",&n)) { memset(cnt,sz=0,sizeof cnt); memset(h,-1,sizeof h); memset(g,0,sizeof g); memset(Ans,0,sizeof Ans); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); cnt[w[i]]++; } for(int i=1;i<=n;i++) cnt[i]=2*cnt[i]; for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } sz=0; dfs(1,-1); for(int i=0;i<2*(n-1);i++) { if(e[i].f==0) continue; q[i/2].L=L[e[i].v]; q[i/2].R=R[e[i].v]; q[i/2].id=i/2; } sz=sqrt(2*n); for(int i=1;i<=2*n;i++) pos[i]=i/sz; sort(q,q+(n-1),cmp); pp=0,qq=0; for(int i=q[0].L;i<=q[0].R;i++) { g[a[i]]++; op2(i); } Ans[q[0].id]=qq-pp; int L=q[0].L,R=q[0].R; for(int i=1;i<n-1;i++) { while(L<q[i].L) { g[a[L]]--; op1(L); L++; } while(L>q[i].L) { L--; g[a[L]]++; op2(L); } while(R>q[i].R) { g[a[R]]--; op1(R); R--; } while(R<q[i].R) { R++; g[a[R]]++; op2(R); } Ans[q[i].id]=qq-pp; } for(int i=0;i<n-1;i++) printf("%d\n",Ans[i]); } return 0;}
CSU 1811 Tree Intersection
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。