fork download
copy 
  1. /*
  2. 树的秘密.(secret.cpp/c/pas)
  3. Prime最近在研究树这种奇怪的数据结构，他把树的意思向周边各位组的大神介绍了一遍：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
  4. 大神们表示不能理解这种奇怪的东西 ，然后Prime又耐心的解释了一遍的树的意思，Prime讲数据结构就好比张三丰教张无忌太极一样，每一遍都不一样!他这次是这样解释的：单个结点是一棵树，树根就是该结点本身。
  5. 设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。
  6. 空集合也是树，称为空树。空树中没有结点。
  7. 好吧，大神们纷纷的懂了树的意思，于是好奇的他们每人给prime出了一个问题。
  8. 蕾蕾想知道树上任意两点之间的路径权值和是多少，他认为他期末考试的分数是这个和的1000倍！
  9. 陶爷，是一个文艺沉静的大神，他觉得树应有一种静美，所以他希望知道任意两点之间的路径中权值最大的一条边是什么，以便他写文章来讽刺这条边！
  10. ZCJ是一个爱闹事的XAG逗比,他会不时的改变某一条的边的权值，但是他技术太弱，不会改变边所连是哪对节点。
  11. 树是在是一种神秘的数据结构，prime表示他参透不了其中的秘密！
  12. 这时Prime周围的tty,owaski,lyx,zxo以及众大神开始嘲讽prime太弱，肯定解决不了，是的Prime他好弱啥都不会，于是他把问题交给了大神您，谢谢你！
  13.  
  14. */
  15. #include <cstdio>
  16. #include <cstdlib>
  17. #include <cstring>
  18. #include <iostream>
  19. #include <algorithm>
  20. #include <cmath>
  21. #include <ctime>
  22. #include <queue>
  23. #include <set>
  24. #include <map>
  25. #define REP(I,A,B) for(int I=A,END=B;I<=END;I++)
  26. #define REPD(I,A,B) for(int I=A,END=B;I>=END;I--)
  27. #define RI(X) scanf("%d",&X)
  28. #define RS(X) scanf("%s",&X)
  29. #define GCH getchar()
  30. #define PCH(X) putchar(X)
  31. #define MAX(A,B) (((A)>(B))?(A):(B))
  32. #define MIN(A,B) (((A)<(B))?(A):(B))
  33. #define MS(X,Y) memset(X,Y,sizeof(X))
  34. #define MC(X,Y,var,len) memcpy((X),(Y),sizeof(var)*(len))
  35. #define debug(...) fprintf(stderr,__VA_ARGS__)
  36. #define MAXN 100005
  37. struct line
  38. {
  39.   int y;
  40.   int value;
  41.   int next;
  42. }bian[MAXN*2]={0};
  43. int head[MAXN]={0};
  44. int fa[MAXN]={0};
  45. struct node
  46. {
  47.   int deep;
  48.   int fa;
  49.   int son;
  50.   int w;
  51.   int size;
  52.   int top;
  53. }tree[MAXN]={0};
  54. struct sg_tree
  55. {
  56.   int lazy;
  57.   int max;
  58.   int sum;
  59. }sg[MAXN*4]={0};
  60. int n,m,tot=0;
  61. using namespace std;
  62. void open()
  63. {
  64.   freopen("secret.in","r",stdin);
  65.   freopen("secret.out","w",stdout);
  66. }
  67. void close()
  68. {
  69.   fclose(stdin);
  70.   fclose(stdout);
  71. }
  72. void add(int x,int y,int value)
  73. {
  74.   tot++;
  75.   bian[tot].y=y;
  76.   bian[tot].value=value;
  77.   bian[tot].next=head[x];
  78.   head[x]=tot;
  79. }
  80. void init()
  81. {
  82.   RI(n);
  83.   RI(m);
  84.   int x,y,value;
  85.   REP(i,1,n-1)
  86.   {
  87.     RI(x);
  88.     RI(y);
  89.     RI(value);
  90.     add(x,y,value);
  91.     add(y,x,value);
  92.   }
  93. }
  94. void dfs(int p)//求 deep fa size son 
  95. {
  96.   int i;
  97.   tree[p].size++;
  98.   for (i=head[p];i!=0;i=bian[i].next)
  99.     if (tree[bian[i].y].deep==0) 
  100.     {
  101.       tree[bian[i].y].deep=tree[p].deep+1;
  102.       tree[bian[i].y].fa=p;
  103.       dfs(bian[i].y);
  104.       if (tree[tree[p].son].size<tree[bian[i].y].size)
  105.       {
  106. 	    tree[p].son=bian[i].y;
  107. 	  }
  108. 	  tree[p].size+=tree[bian[i].y].size;
  109.     }
  110. }
  111. void decomposition(int p)
  112. {
  113.   int i;
  114.   if (tree[p].son!=0)
  115.   {
  116.     tree[tree[p].son].top=tree[p].top;
  117.     tot++;
  118.     tree[tree[p].son].w=tot;
  119.     decomposition(tree[p].son);
  120.   }
  121.   for (i=head[p];i!=0;i=bian[i].next)
  122.     if (tree[p].fa!=bian[i].y && tree[p].son!=bian[i].y)
  123.     {
  124. 	  tree[bian[i].y].top=bian[i].y;
  125. 	  tot++;
  126. 	  tree[bian[i].y].w=tot;
  127. 	  fa[tot]=bian[i].value;
  128. 	  decomposition(bian[i].y);
  129. 	}
  130. 	else if (tree[p].son==bian[i].y)
  131. 	{
  132. 	  fa[tree[tree[p].son].w]=bian[i].value;
  133. 	}
  134. }
  135. #define lc(p) (p*2)
  136. #define rc(p) (p*2+1)
  137. void down(int p,int l,int r)
  138. {
  139.   int mid=(l+r)/2;
  140.    if (sg[p].lazy!=0)
  141.    {
  142.      sg[rc(p)].max=sg[lc(p)].max=sg[p].lazy;
  143.      sg[lc(p)].sum=(mid-l+1)*sg[p].lazy;
  144.      sg[rc(p)].sum=(r-mid)*sg[p].lazy;
  145.      sg[rc(p)].lazy=sg[lc(p)].lazy=sg[p].lazy;
  146.      sg[p].lazy=0;
  147.    }
  148. }
  149. void up(int p)
  150. {
  151.   sg[p].max=max(sg[lc(p)].max,sg[rc(p)].max);
  152.   sg[p].sum=sg[lc(p)].sum+sg[rc(p)].sum;
  153. }
  154. void insert(int p,int l,int r,int ll,int rr,int value)
  155. {
  156.   if (l==ll && r==rr)
  157.   {
  158.     sg[p].lazy=value;
  159.     sg[p].max=value;
  160.     sg[p].sum=(r-l+1)*value;
  161.     return ;
  162.   }
  163.   int mid=(l+r)/2;
  164.   down(p,l,r);
  165.   if (rr<=mid)
  166.     insert(lc(p),l,mid,ll,rr,value);
  167.   else if (mid<ll)
  168.     insert(rc(p),mid+1,r,ll,rr,value);
  169.   else 
  170.     insert(lc(p),l,mid,ll,mid,value),insert(rc(p),mid+1,r,mid+1,rr,value);
  171.   up(p);
  172. }
  173. int squery(int p,int l,int r,int ll,int rr)
  174. {
  175.   if (l==ll && r==rr)
  176.   {
  177.     return sg[p].sum;
  178.   }
  179.   int mid=(l+r)/2;
  180.   down(p,l,r);
  181.   if (rr<=mid)
  182.     return squery(lc(p),l,mid,ll,rr);
  183.   else if (mid<ll)
  184.     return squery(rc(p),mid+1,r,ll,rr);
  185.   else
  186.     return squery(lc(p),l,mid,ll,mid)+squery(rc(p),mid+1,r,mid+1,rr);
  187. }
  188. int mquery(int p,int l,int r,int ll,int rr)
  189. {
  190.   if (l==ll && r==rr)
  191.   {
  192.     return sg[p].max;
  193.   }
  194.   int mid=(l+r)/2;
  195.   down(p,l,r);
  196.   if (rr<=mid)
  197.     return mquery(lc(p),l,mid,ll,rr);
  198.   else if (mid<ll)
  199.     return mquery(rc(p),mid+1,r,ll,rr);
  200.   else
  201.     return max(mquery(lc(p),l,mid,ll,mid),mquery(rc(p),mid+1,r,mid+1,rr));
  202. }
  203. void maketree()
  204. {
  205.   REP(i,1,n)
  206.     insert(1,1,n,tree[i].w,tree[i].w,fa[tree[i].w]);
  207. }
  208. int sfind(int u,int v)
  209. {
  210.   int fu=tree[u].top,fv=tree[v].top;
  211.   int sum=0;
  212.   while (fu!=fv)
  213.   {
  214.     if (tree[fu].deep<tree[fv].deep)
  215.     {
  216. 	  swap(u,v);
  217. 	  swap(fu,fv);
  218. 	}
  219. 	sum+=squery(1,1,n,tree[fu].w,tree[u].w);
  220. 	u=tree[fu].fa;
  221. 	fu=tree[u].top;
  222.   }
  223.   if (u==v) //已然是LCA
  224.   {
  225.     return sum;
  226.   } 
  227.   else if (tree[u].deep>tree[v].deep)
  228.   {
  229.     swap(u,v);
  230.   }
  231.   return sum+squery(1,1,n,tree[tree[u].son].w,tree[v].w);
  232. }
  233. int mfind(int u,int v)
  234. {
  235.   int fu=tree[u].top,fv=tree[v].top;
  236.   int tmp=0;
  237.   while (fu!=fv)
  238.   {
  239.     if (tree[fu].deep<tree[fv].deep)
  240.     {
  241. 	  swap(u,v);
  242. 	  swap(fu,fv);
  243. 	}
  244. 	tmp=max(tmp,mquery(1,1,n,tree[fu].w,tree[u].w));
  245. 	u=tree[fu].fa;
  246. 	fu=tree[u].top;
  247.   }
  248.   if (u==v)
  249.   {
  250.     return tmp;
  251.   }
  252.   else if (tree[u].deep>tree[v].deep)
  253.   {
  254.     swap(u,v);
  255.   }
  256.   return max(tmp,mquery(1,1,n,tree[tree[u].son].w,tree[v].w));
  257. }
  258. void change(int u,int v,int value)
  259. {
  260.   int fu=tree[u].top,fv=tree[v].top;
  261.   while (fu!=fv)
  262.   {
  263.     if (tree[fu].deep<tree[fv].deep)
  264.     {
  265. 	  swap(u,v);
  266. 	  swap(fu,fv);
  267. 	}
  268. 	insert(1,1,n,tree[fu].w,tree[u].w,value);
  269. 	u=tree[fu].fa;
  270. 	fu=tree[u].top;
  271.   }
  272.   if (u==v)
  273.   {
  274.     return ;
  275.   }
  276.   else if (tree[u].deep>tree[v].deep)
  277.   {
  278.     swap(u,v);
  279.   }
  280.   insert(1,1,n,tree[tree[u].son].w,tree[v].w,value);
  281. }
  282. void work()
  283. {
  284.   scanf("\n");
  285.   char way;
  286.   int x,y,value;
  287.   REP(_,1,m)
  288.   {
  289.     way=GCH;
  290.     GCH;
  291.     GCH;
  292.     RI(x);
  293.     RI(y);
  294.     if (way=='C')
  295.     {
  296. 	  RI(value);
  297. 	  change(x,y,value);
  298. 	}
  299.     else if (way=='S')
  300.     {
  301. 	  printf("%d\n",sfind(x,y));
  302. 	}
  303. 	else
  304. 	{
  305. 	  printf("%d\n",mfind(x,y));
  306. 	}
  307.     GCH;
  308.   }
  309. }
  310. int main()
  311. {
  312.   open();
  313.   init();
  314.   tree[1].deep=1;
  315.   dfs(1);
  316.   tot=0;
  317.   tot++;
  318.   tree[1].w=tot;
  319.   tree[1].top=1;
  320.   fa[1]=0;
  321.   decomposition(1);
  322.   maketree();
  323.   work();
  324.   close();
  325.   return 0;
  326. }
Success #stdin #stdout 0s 13296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bLgmno
secret
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!