題目鏈接：點擊查看

題目大意：給出一棵無向樹，每個節點都有一種顏色，接下來時m次操作：

1 x y：將x及其子樹染成y的顏色

2 x：查詢x及其子樹上共有多少種不同的顏色

題目分析：看完這個題的第一反應就是直接暴力跑跑試試，因為樹的話時間復雜度是logn，暴力的話也才nlogn，可是等WA了一發后我才意識到，logn級別的是二叉樹才能實現的時間精度，如果最差的情況，樹是一條直線分布，那時間復雜度到了n*n，在這個題目中必然超時，但給我的結果時WA我還是有點意外的。。所以我們需要考慮另外的方法，因為這個題目是放在了線段樹的專題中，而且時關于子樹的操作，我們可以先將每個點用dfs序排個序，將每個頂點的子樹放到一起，將樹線性化，這樣就能將對子樹的一系列操作轉換為對區間的一系列操作，進而可以在線段樹上進行操作，達到真正查找和修改都是logn的時間復雜度了。關于對顏色種類的處理可以使用狀態壓縮，之前做過一個很類似的題目。

補充一下，有個細節，之前都沒注意到過的，就是對狀態進行壓縮時，要用longlong這個沒問題，就是(1<<i)這個語句，一定一定要記得在1后面加上一個LL，寫成這樣才行：(1LL<<i)，因為這個細節，WA了一晚上

直接上代碼吧，更多的會在注釋中解釋：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e5+100;int a[N];int cnt;LL color[N];int point[N];int num[N];//dfs的時候順便記錄一下子樹上的節點數量，可以依次來確定子樹所在的區間vector<int>node[N];void dfs(int u,int fa)//dfs序給每個節點編號 {num[u]=1;color[cnt]=(1LL<<a[u]);point[u]=cnt++;for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;if(num[v])continue;dfs(v,u);num[u]+=num[v];} }struct Node//線段樹維護區間顏色狀態，和之前做過的一個題很類似 {int l,r;LL color;bool lazy; }tree[N<<2];void pushup(int k) {tree[k].color=(tree[k<<1].color|tree[k<<1|1].color); }void pushdown(int k) {tree[k<<1].lazy=tree[k<<1|1].lazy=true;tree[k<<1].color=tree[k<<1|1].color=tree[k].color;tree[k].lazy=false; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=false;if(l==r){tree[k].color=color[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].color=(1LL<<val);tree[k].lazy=true;return;}if(tree[k].lazy)pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].color;if(tree[k].lazy)//這里不要忘記下傳懶標記pushdown(k);return query(k<<1,l,r)|query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){scanf("%d",a+i);node[i].clear();}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}memset(num,0,sizeof(num));memset(color,0,sizeof(color));memset(point,0,sizeof(point));cnt=1;dfs(1,-1);build(1,1,n);while(m--){int op;scanf("%d",&op);if(op==1){int x,y;scanf("%d%d",&x,&y);update(1,point[x],point[x]+num[x]-1,y);}else{int x;scanf("%d",&x);LL ans=query(1,point[x],point[x]+num[x]-1);int tt=0;while(ans){if(ans&1)tt++;ans>>=1;}printf("%d\n",tt);}}}return 0; }

后來做題又學會了一種我感覺比較好的dfs序的方法，就是用L和R兩個數組來維護某個點的子樹區間：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e5+100;int a[N];int cnt;LL color[N];int L[N],R[N];vector<int>node[N];void dfs(int u,int fa) {L[u]=++cnt;color[cnt]=(1LL<<a[u]);for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs(v,u);}R[u]=cnt; }struct Node {int l,r;LL color;bool lazy; }tree[N<<2];void pushup(int k) {tree[k].color=(tree[k<<1].color|tree[k<<1|1].color); }void pushdown(int k) {tree[k<<1].lazy=tree[k<<1|1].lazy=true;tree[k<<1].color=tree[k<<1|1].color=tree[k].color;tree[k].lazy=false; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=false;if(l==r){tree[k].color=color[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].color=(1LL<<val);tree[k].lazy=true;return;}if(tree[k].lazy)pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].color;if(tree[k].lazy)pushdown(k);return query(k<<1,l,r)|query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){scanf("%d",a+i);node[i].clear();}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}memset(color,0,sizeof(color));cnt=0;dfs(1,-1);build(1,1,n);while(m--){int op;scanf("%d",&op);if(op==1){int x,y;scanf("%d%d",&x,&y);update(1,L[x],R[x],y);}else{int x;scanf("%d",&x);LL ans=query(1,L[x],R[x]);int tt=0;while(ans){if(ans&1)tt++;ans>>=1;}printf("%d\n",tt);}}}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 620E New Year Tree(线段树+dfs序+状态压缩)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。