[BZOJ2243][SDOI2011]染色

2243: [SDOI2011]染色

Time Limit: 20 Sec Memory Limit: 512 MB Submit: 8463 Solved: 3168 [Submit][Status][Discuss]

Description

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

Sample Output

3

1

2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

树剖裸题

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 int n,m;
  9 int c[400005];
 10 struct data {
 11     int next,to;
 12 }e[400005];
 13 int head[400005],cnt;
 14 void add(int u,int v){e[cnt].next=head[u];e[cnt].to=v;head[u]=cnt;cnt++;}
 15 int son[400005],size[400005],fa[400005],dep[400005];
 16 void findson(int now) {
 17     size[now]=1;
 18     for(int i=head[now];i>=0;i=e[i].next) {
 19         int to=e[i].to;
 20         if(to==fa[now]) continue;
 21         fa[to]=now;
 22         dep[to]=dep[now]+1;
 23         findson(to);
 24         size[now]+=size[to];
 25         if(size[to]>size[son[now]]) son[now]=to;
 26     }
 27 }
 28 int up[400005],id[400005],p[400005],s;
 29 void dfs(int now,int top) {
 30     id[now]=++s;
 31     p[s]=now;
 32     up[now]=top;
 33     if(son[now]) dfs(son[now],top);
 34     for(int i=head[now];i>=0;i=e[i].next) {
 35         int to=e[i].to;
 36         if(to==fa[now]||to==son[now]) continue;
 37         dfs(to,to);
 38     }
 39 }
 40 struct te {
 41     int lc,rc,color,l,r,lazy;
 42 }t[800005];
 43 void pushup(int now) {
 44     int l=now<<1,r=l|1;
 45     t[now].lc=t[l].lc;t[now].rc=t[r].rc;
 46     t[now].color=t[l].color+t[r].color;
 47     if(t[l].rc==t[r].lc) t[now].color--;
 48 }
 49 void pushdown(int now) {
 50     if(!t[now].lazy) return;
 51     int l=now<<1,r=l|1;
 52     t[l].lazy=t[l].lc=t[l].rc=t[r].lazy=t[r].lc=t[r].rc=t[now].lazy;
 53     t[l].color=t[r].color=1;
 54     t[now].lazy=0;
 55 }
 56 void build(int now,int l,int r) {
 57     t[now].l=l;t[now].r=r;
 58     if(l==r){t[now].color=1;t[now].lc=t[now].rc=c[p[l]];return;}
 59     else {
 60         int mid=(l+r)>>1;
 61         build(now<<1,l,mid);
 62         build(now<<1|1,mid+1,r);
 63     }
 64     pushup(now);
 65 }
 66 void update(int now,int L,int R,int c) {
 67     int l=t[now].l,r=t[now].r;
 68     pushdown(now);
 69     if(L<=l&&R>=r){t[now].lc=t[now].rc=t[now].lazy=c;t[now].color=1;return;}
 70     else {
 71         int mid=(l+r)>>1;
 72         if(L<=mid) update(now<<1,L,R,c);
 73         if(R>mid) update(now<<1|1,L,R,c);
 74     }
 75     pushup(now);
 76 }
 77 int findlca(int a,int b) {
 78     int x,y;
 79     x=up[a],y=up[b];
 80     while(x!=y) {
 81         if(dep[x]<dep[y]) swap(x,y),swap(a,b);
 82         a=fa[x];x=up[a];
 83     }
 84     if(dep[a]<dep[b]) swap(a,b);
 85     return b;
 86 }
 87 int query(int now,int L,int R) {
 88     int ans=0;
 89     int l=t[now].l,r=t[now].r;
 90     pushdown(now);
 91     if(L<=l&&R>=r) return t[now].color;
 92     else {
 93         int mid=(l+r)>>1;
 94         if(R<=mid) ans+=query(now<<1,L,R);
 95         else if(L>mid) ans+=query(now<<1|1,L,R);
 96         else {
 97             ans+=query(now<<1,L,R)+query(now<<1|1,L,R);
 98             if(t[now<<1].rc==t[now<<1|1].lc) ans--;
 99         }
100     }
101     return ans;
102 }
103 void change(int now,int lca,int c) {
104     while(up[now]!=up[lca]) {
105         update(1,id[up[now]],id[now],c);
106         now=fa[up[now]];
107     }
108     update(1,id[lca],id[now],c);
109 }
110 int getc(int now,int x) {
111     pushdown(now);
112     int l=t[now].l,r=t[now].r;
113     if(l==r) return t[now].lc;
114     int mid=(l+r)>>1;
115     if(x<=mid)return getc(now<<1,x);
116     else return getc(now<<1|1,x);
117 }
118 int ask(int now,int lca) {
119     int ans=0;
120     while(up[now]!=up[lca]) {
121         ans+=query(1,id[up[now]],id[now]);
122         if(getc(1,id[up[now]])==getc(1,id[fa[up[now]]])) ans--;
123         now=fa[up[now]];
124     }
125     return ans+query(1,id[lca],id[now]);
126 }
127 int main() {
128     memset(head,-1,sizeof(head));
129     scanf("%d%d",&n,&m);
130     for(int i=1;i<=n;i++) scanf("%d",&c[i]);
131     for(int i=1;i<=n-1;i++) {
132         int u,v;
133         scanf("%d%d",&u,&v);
134         add(u,v);add(v,u);
135     }
136     dep[1]=1;
137     findson(1);dfs(1,1);build(1,1,n);
138     for(int i=1;i<=m;i++) {
139         char ch[10];
140         scanf("%s",ch);
141         if(ch[0]=='C') {
142             int a,b,c;
143             scanf("%d%d%d",&a,&b,&c);
144             int lca=findlca(a,b);
145             change(a,lca,c);change(b,lca,c);
146         }
147         else {
148                int a,b;
149                scanf("%d%d",&a,&b);
150                int lca=findlca(a,b);
151                printf("%d
",ask(a,lca)+ask(b,lca)-1);
152         }
153     }
154 }

View Code

O(∩_∩)O~ (*^__^*) 嘻嘻…… O(∩_∩)O哈哈~