[Educational Codeforces Round 6][Codeforces 620E]New Year Tree
题意：给出一棵以1为根的树，每个节点有一个颜色，颜色数<=60。有两种操作，操作1为将一棵以v为根的子树中的所有节点颜色变为ai，操作2为查询以v为根的子树中的所有节点有多少种不同颜色。
题解：考虑到颜色最多只有60种，所以可以用一个long long按位来记录颜色是否出现。对整棵树做出DFS序，然后建线段树，然后就是区间查询区间修改就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <bits/stdc++.h>using namespace std;const int maxn=7e5+10;struct Segment_Tree{ #define ls (o<<1) #define rs ((o<<1)|1) #define mid ((l+r)>>1) int tag[maxn<<1]; long long v[maxn<<1]; void Update(int o) { v[o]=v[ls]|v[rs]; } void Mark_Same(int o,int tg) { v[o]=1ll<<(tg-1); tag[o]=tg; } void Push_Down(int o) { if (!tag[o]) return; Mark_Same(ls,tag[o]); Mark_Same(rs,tag[o]); tag[o]=0; } void Change(int o,int l,int r,int a,int b,int tg) { if (a<=l && r<=b) { Mark_Same(o,tg); return; } Push_Down(o); if (a<=mid) Change(ls,l,mid,a,b,tg); if (b> mid) Change(rs,mid+1,r,a,b,tg); Update(o); } long long Query(int o,int l,int r,int a,int b) { if (a<=l && r<=b) return v[o]; Push_Down(o); long long res=0; if (a<=mid) res|=Query(ls,l,mid,a,b); if (b> mid) res|=Query(rs,mid+1,r,a,b); Update(o); return res; } void Build(int o,int l,int r,int *cor) { if (l==r) { v[o]=1ll<<(cor[l]-1); return; } Build(ls,l,mid,cor); Build(rs,mid+1,r,cor); Update(o); }}T;int head[maxn],nxt[maxn<<1],E[maxn<<1],Ecnt;int dfsq[maxn],tmp[maxn];int l[maxn],r[maxn],Index;int cor[maxn];int n,m;void Add_Edge(int x,int y) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}void DFS(int x,int father=0){ l[x]=++Index; dfsq[Index]=x; for (int i=head[x];i;i=nxt[i]) if (E[i]!=father) DFS(E[i],x); r[x]=Index;}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&cor[i]); for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add_Edge(x,y); DFS(1); for (int i=1;i<=n;i++) tmp[i]=cor[dfsq[i]]; T.Build(1,1,n,tmp); while (m--) { int t,v,c; scanf("%d",&t); if (t==1) { scanf("%d%d",&v,&c); T.Change(1,1,n,l[v],r[v],c); } else { scanf("%d",&v); long long res=T.Query(1,1,n,l[v],r[v]); int ans=0; while (res) { ans+=res%2; res>>=1; } printf("%d\n",ans); } } return 0;} |
评论 (0)
