fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <algorithm>
  5. #define REP(I,A,B) for(int I=A,END=B;I<=END;I++)
  6. #define REPD(I,A,B) for(int I=A,END=B;I>=END;I--)
  7. #define RI(X) scanf("%d",&X)
  8. #define RS(X) scanf("%s",&X)
  9. #define GCH getchar()
  10. #define B(I) biao[I] 
  11. #define debug(...) fprintf(stderr,__VA_ARGS__)
  12. #define T(I) tree[I]
  13. #define root (1)
  14. #define MAXN 100005
  15. struct adj
  16. {
  17.  
  18.   int y;
  19.   adj *next;
  20. }*biao[MAXN]={0};
  21. struct node
  22. {
  23.   int son;//重儿子
  24.   int w; //点所在线段树の位置 
  25.   int size; //大小 
  26.   int deep; //深度 
  27.   int fa;  //父亲 
  28.   int top; //链顶 
  29. }tree[MAXN]={{0}};
  30. struct segment
  31. {
  32.   int tot;//总颜色数
  33.   int lc; //左端点颜色
  34.   int rc; //右端点颜色 
  35.   int lazy; //lazy
  36. }st[MAXN<<2]={{0}};
  37. using namespace std;
  38. int color[MAXN]={0};
  39. int n,m;
  40. int id=0;
  41. void open()
  42. {
  43.   freopen("paint.in","r",stdin);
  44.   freopen("paint.out","w",stdout);
  45. }
  46. void close()
  47. {
  48.   fclose(stdin);
  49.   fclose(stdout);
  50. }
  51. void add(int x,int y)
  52. {
  53.   adj *p=(adj *)malloc(sizeof(adj));
  54.   p->y=y;
  55.   p->next=B(x);
  56.   B(x)=p;
  57. }
  58. /*
  59. void dfs(int p)//son size deep fa 
  60. {
  61.   T(p).size=1;
  62.   T(p).deep=T(T(p).fa).deep+1;
  63.   for (adj *i=B(p);i!=NULL;i=i->next)
  64.     if (i->y!=T(p).fa)
  65.     {
  66. 	  T(i->y).fa=p;
  67. 	  dfs(i->y);
  68. 	  if (T(i->y).size>T(T(p).son).size)
  69. 	    T(p).son=i->y;
  70. 	  T(p).size+=T(i->y).size;
  71. 	}
  72. }*/
  73. /*
  74. 这个应该改成BFS版本求son size deep fa 
  75. 只要先搜一遍，在搜回去 
  76. */
  77. int queue[MAXN]={0};
  78. inline void BFS()
  79. {
  80.   int head,tail;
  81.   int i;
  82.   adj *j;
  83.   int x;
  84.   head=tail=1;
  85.   queue[head]=root;
  86.   T(root).deep=1;
  87.   T(root).fa=0;
  88.   T(root).size=1;
  89.   while (head<=tail)
  90.   {
  91.     i=queue[head];
  92.     head++;
  93.     for (j=B(i);j!=NULL;j=j->next) 
  94.     {
  95.       x=j->y;
  96.       if (x!=T(i).fa)
  97.       {
  98.       	tail++;
  99. 	    queue[tail]=x;
  100. 	    T(x).fa=i;
  101. 	    T(x).deep=T(i).deep+1;
  102. 	    T(x).size=1;
  103. 	  }
  104.     }
  105.   }
  106.   REPD(prime,tail,1)
  107.   {
  108.     i=queue[prime];
  109.     for (j=B(i);j!=NULL;j=j->next)
  110.     {
  111. 	  x=j->y;
  112. 	  if (x!=T(i).fa)
  113. 	  {
  114. 	    T(i).size+=T(x).size;
  115. 	    if (T(x).size>T(T(i).son).size) T(i).son=x;
  116. 	  }
  117. 	}
  118.   }
  119. }
  120. inline void decomposition(int p)
  121. {
  122.   int j;
  123.   adj *i;
  124.   T(p).w=++id;//记录位置
  125.   if (T(p).son!=0)
  126.   {
  127.   	j=T(p).son;
  128.   	T(j).top=T(p).top;
  129.     decomposition(j);
  130.   } 
  131.   for (i=B(p);i!=NULL;i=i->next)
  132.   {
  133.     j=i->y;
  134.     if (j!=T(p).fa && j!=T(p).son)
  135.     {
  136. 	  T(j).top=j;
  137. 	  decomposition(j);
  138. 	}
  139.   }
  140. }
  141. inline void down(int p)
  142. {
  143.   int lch;
  144.   int rch;
  145.   if (st[p].lazy!=-1)
  146.   {
  147.   	lch=p*2;
  148.   	rch=p*2+1;
  149.     st[lch].lazy=st[rch].lazy=st[p].lazy;
  150.     st[lch].lc=st[lch].rc=st[rch].lc=st[rch].rc=st[p].lazy;
  151.     st[lch].tot=st[rch].tot=1;
  152.     st[p].lazy=-1;
  153.   }
  154. }
  155. inline void up(int p)
  156. {
  157.   int lch=p*2;
  158.   int rch=p*2+1;
  159.   st[p].lc=st[lch].lc;
  160.   st[p].rc=st[rch].rc;
  161.   st[p].tot=st[lch].tot+st[rch].tot-(st[lch].rc==st[rch].lc);
  162. }
  163. inline segment query(int p,int l,int r,int ll,int rr)
  164. {
  165.   if (ll==l && rr==r)
  166.   {
  167.     return st[p];
  168.   }
  169.   else
  170.   {
  171.     int mid=(l+r)/2;
  172.     down(p);
  173.     if (rr<=mid)
  174.     {
  175. 	  return query(p*2,l,mid,ll,rr);
  176. 	}
  177. 	else if (mid<ll)
  178. 	{
  179. 	  return query(p*2+1,mid+1,r,ll,rr);
  180. 	}
  181. 	else 
  182. 	{
  183. 	  segment lch=query(p*2,l,mid,ll,mid);
  184. 	  segment rch=query(p*2+1,mid+1,r,mid+1,rr);
  185. 	  segment tmp;
  186. 	  tmp.lc=lch.lc;
  187. 	  tmp.rc=rch.rc;
  188. 	  tmp.tot=lch.tot+rch.tot-(lch.rc==rch.lc);
  189. 	  return tmp;
  190. 	}
  191.   }
  192. }
  193. inline void update(int p,int l,int r,int ll,int rr,int value)
  194. {
  195.   if (ll==l && rr==r)
  196.   {
  197.     st[p].lc=value;
  198.     st[p].rc=value;
  199.     st[p].tot=1;
  200.     st[p].lazy=value;//颜色lazy 
  201.   }
  202.   else
  203.   {
  204.     int mid=(l+r)/2;
  205.     down(p);//先标记下传. 
  206.     if (rr<=mid)
  207.     {
  208. 	  update(p*2,l,mid,ll,rr,value);
  209. 	}
  210. 	else if (mid<ll)
  211. 	{
  212. 	  update(p*2+1,mid+1,r,ll,rr,value);
  213. 	}
  214. 	else 
  215. 	{
  216. 	  update(p*2,l,mid,ll,mid,value);
  217. 	  update(p*2+1,mid+1,r,mid+1,rr,value);
  218. 	}
  219. 	up(p);//修改p 
  220.   }
  221. }
  222. inline void built_segment()
  223. {
  224.   REP(i,1,n)
  225.   {
  226.     update(1,1,id,T(i).w,T(i).w,color[i]); 
  227.   }
  228. }
  229. inline void init()
  230. {
  231.   int x,y;
  232.   RI(n);
  233.   RI(m);
  234.   REP(i,1,n)
  235.     RI(color[i]);
  236.   REP(i,1,n-1)
  237.   {
  238.     RI(x);
  239.     RI(y);
  240.     add(x,y);
  241.     add(y,x);
  242.   }
  243.   T(root).fa=0;
  244.   BFS();
  245.   T(root).top=root;
  246.   id=0;
  247.   decomposition(root);
  248.   built_segment(); 
  249. }
  250. inline void paint(int u,int v,int color)
  251. {
  252.   int fu=T(u).top,fv=T(v).top;
  253.   while(fu!=fv)
  254.   {
  255.     if (T(fu).deep<T(fv).deep)
  256.     {
  257. 	  swap(fu,fv);
  258. 	  swap(u,v);
  259. 	}
  260. 	update(1,1,id,T(fu).w,T(u).w,color);
  261. 	u=T(fu).fa;
  262. 	fu=T(u).top;
  263.   }
  264.   //写丑了这里可以和后面合并 
  265.   if (u==v) //提到同一个位置了 
  266.   {
  267.     update(1,1,id,T(u).w,T(u).w,color);
  268.     return ;
  269.   }
  270.   if (T(u).deep>T(v).deep)
  271.   {
  272.     swap(u,v);
  273.   }
  274.   update(1,1,id,T(u).w,T(v).w,color);
  275. }
  276. inline int find(int u,int v)
  277. {
  278.   int fu=T(u).top,fv=T(v).top;
  279.   int ans=0,ulc=-1,vlc=-1;
  280.   segment tmp;
  281.   /*
  282.     开始逗比了，只记录了
  283.     一个左的位置。。没有发现是两个点一起向上走么 
  284.   */		 
  285.   while (fu!=fv)
  286.   {
  287.     if(T(fu).deep<T(fv).deep)
  288.     {
  289. 	  swap(fu,fv);
  290. 	  swap(u,v);
  291. 	  swap(ulc,vlc);
  292. 	}
  293. 	tmp=query(1,1,id,T(fu).w,T(u).w);
  294. 	ans+=tmp.tot-(tmp.rc==ulc);
  295. 	ulc=tmp.lc;
  296. 	u=T(fu).fa;
  297. 	fu=T(u).top;
  298.   }
  299.   //跪跪的发现一点，反正 u==y也要修改 
  300.   if (T(u).deep>T(v).deep)
  301.   {
  302.     swap(u,v);
  303.     swap(ulc,vlc);
  304.   }
  305.   tmp=query(1,1,id,T(u).w,T(v).w);
  306.   //这一段真心奇葩 ulc与 tmp.lc相交 vlc与tmp.rc
  307.   ans+=tmp.tot-(ulc==tmp.lc)-(vlc==tmp.rc);
  308.   return ans;
  309. }
  310. inline void work()
  311. {
  312.   char way;
  313.   int a,b,c;
  314.   GCH;
  315.   REP(i,1,m)
  316.   {
  317.   	way=GCH;
  318.   	if (way=='C')
  319.   	{
  320.   	  RI(a);
  321.   	  RI(b);
  322.   	  RI(c);
  323.   	  GCH; 
  324.       paint(a,b,c); 
  325.     }
  326.     else 
  327.     {
  328. 	  RI(a);
  329. 	  RI(b);
  330. 	  GCH;
  331. 	  printf("%d\n",find(a,b));
  332. 	}
  333.   }
  334. }
  335. int main()
  336. {
  337.   open();
  338.   init();
  339.   work();
  340.   close();
  341.   return 0;
  342. }
Success #stdin #stdout 0s 12880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SeQ7y0
SDOI2011染色
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!