fork download
copy 
  1. /*
  2. SPOJ 375
  3. 一道树链剖分的好题。
  4. 先讲一讲树链剖分。
  5. 树链剖分有很多种，我们一般用的是轻重边路径剖分
  6. 首先熟悉一些定义：
  7. size[v]--以v为根的子树的节点数
  8. deep[v]--v的深度
  9. father[v]--v的父亲
  10.  
  11.  
  12. 然后我们定义一些东西。
  13. 重儿子:w size[w]为v的子节点种size最大的，记w为v的重儿子
  14. 轻儿子: v的其他儿子
  15. 重边: 点V与其重儿子的连边
  16. 轻边: 有重边连成的路径。
  17. 重链: 由重边连成的路径。(我们也叫它树链)
  18.  
  19. 可以发现如下性质
  20. 性质1： (u,v)为轻边 size(v)<=size(u)/2
  21. 性质2:  从根到某一点的路径上轻边的个数不大于O(logN)
  22. 性质3:  重链上的所有路径都是重边，每个点到根的路径不超过O(logN)轻边&O(logN)重路径 
  23.  
  24. 我们如何表示一颗链:
  25. top[v]--v所在的重链的根
  26. son[v]--v的重儿子
  27. w[v]--v连到父亲的边（父边）在线段树中的位置 
  28.  
  29. 下面如何求算这些东西
  30. dfs1:size deep fa son
  31. 这四个是树的DFS的最基本算法了
  32. dfs2:w top
  33. 考虑到如下结论
  34. 有儿子先考虑重儿子扩展！ 
  35. 1.重儿子和本身在同一根重链上，即:
  36.   top[son[v]]=top[v]
  37. 2.而我们考虑用一颗线段树来维护重链的一些东西
  38.   为了保持一条链上的边在线段树中连续且有序，我们应进行如下操作:
  39.   显然 我们用tot表示最后一条边加入线段树的位置(即v的父边) 
  40.     ①w[son[v]]=tot+1; tot++；(我们并不需要把这条边加入线段树，只需要记录一下它要加在那个位置) (重链入树)
  41.     ②dfs2(son[v])
  42. 3.考虑孤苦伶仃的轻儿子u
  43.   从它开始有重新划分显然
  44.   top[u]=u;
  45.   w[u]=tot+1; tot++; (轻边入树)
  46.   dfs2(u);
  47. 4.我们可以发现树的每一条边都会以父边的形式出现在线段树中 
  48. 而且我们是按照第二遍DFS序加入线段树的
  49. 它可以保证在线段树中，每一条重链的边在一起，每一棵子树的边在一起。
  50. 这给我们的修改和查询带了了方便
  51. 5.修改操作 u-v之间的每一条边都加上一个值
  52.  法①：求u-v的LCA然后直接往上面修改
  53.  法②：根据我们保存的信息其实已经可以求出LCA了
  54.    Ⅰ 记f1=top[u] f2=top[v] 
  55.    Ⅱ f1!=f2 说明不在同一重链上 
  56.       我们就把离树远的点提到其链的顶端，并查询这一段的最大值
  57. 	  u=fa[f1]/ v=fa[f2] 
  58.    Ⅲ 重复Ⅱ直到 f1==f2 
  59.    Ⅳ 此时两点已在同一条重链上。如果已是同一点直接返回
  60.      否则查询这一段的最大值 
  61.    实际上这就是不求LCA的解法。 
  62. */
  63. #include <cstdio>
  64. #include <cstdlib>
  65. #include <cstring>
  66. #include <ctime>
  67. #include <iostream>
  68. #include <algorithm>
  69. #define REP(I,A,B) for(int END=B,I=A;I<=END;I++)
  70. #define RI(X) scanf("%d",&X)
  71. #define RS(X) scanf("%s",&X)
  72. #define GCH() getchar();
  73. #define INF 1e8
  74. #define MAXN 10005
  75. #define T(X) tree[X].
  76. #define B(X) bian[X].
  77. #define CLEAR(X) memset(X,0,sizeof(X));
  78. #define debug(...) fprintf(stderr ,__VA_ARGS__) 
  79. #define MAX(A,B) ((A)>(B)?(A):(B))
  80. using namespace std;
  81. struct NODE
  82. {
  83.   int fa;
  84.   int deep;
  85.   int size;
  86.   int w;
  87.   int top;
  88.   int son;
  89. }tree[MAXN];
  90. struct edge
  91. {
  92.   int y;
  93.   struct edge *next;
  94. }*bian[MAXN];
  95. struct SYZ
  96. {
  97.   int x;
  98.   int y;
  99.   int cost;
  100. }in[MAXN]={{0}};
  101. struct segment
  102. {
  103.   int max;
  104. }st[MAXN<<2]={{0}};
  105. int root=1;
  106. int n;
  107. int tot;//线段树总长度  非递归线段树！ 
  108. void open()
  109. {
  110.   freopen("qtree.in","r",stdin);
  111.   freopen("qtree.out","w",stdout);
  112. }
  113. void close()
  114. {
  115.   fclose(stdin);
  116.   fclose(stdout);
  117. }
  118. void insert(int x,int y,int cost)
  119. {
  120.   edge *p=(edge *)malloc(sizeof(edge));
  121.   p->y=y;
  122.   p->next=bian[x];
  123.   bian[x]=p;
  124. }
  125. void dfs(int p) //求size，deep，father, son(重儿子) 
  126. {
  127.   edge *i=bian[p];
  128.   int j;
  129.   T(p)size=1;
  130.   T(p)son=0;  //表示没有孩子
  131.   for (;i!=NULL;i=i->next)
  132.     if (T(p)fa!=i->y)
  133.     {
  134. 	  j=i->y;
  135. 	  T(j)fa=p;
  136. 	  T(j)deep=T(p)deep+1;
  137. 	  dfs(j);
  138. 	  T(p)size+=T(j)size;
  139. 	  if (T(j)size>T(T(p)son)size)
  140. 	    T(p)son=j;
  141. 	}
  142. }
  143. void decomposition(int p)
  144. {
  145.   int j;
  146.   if (T(p)son!=0)
  147.   {
  148.   	j=T(p)son;
  149.     T(j)w=++tot;
  150.     T(j)top=T(p)top;
  151.     decomposition(j);
  152.   }
  153.   //无论如何这个是要更新的。。 
  154.   edge *i=bian[p];
  155.   for (;i!=NULL;i=i->next)
  156.     if (i->y!=T(p)son && i->y!=T(p)fa) 
  157. 	{
  158. 	  j=i->y;
  159. 	  T(j)top=j;
  160. 	  T(j)w=++tot;
  161. 	  decomposition(j);
  162. 	} 
  163. }
  164. void update(int p,int l,int r,int aim,int value)
  165. {
  166.   if (l==r)
  167.   {
  168.     st[p].max=value;
  169.   }
  170.   else 
  171.   {
  172.     int mid=(l+r)/2;
  173.     if (aim<=mid)
  174.     {
  175. 	  update(p*2,l,mid,aim,value);
  176. 	}
  177. 	else 
  178. 	{
  179. 	  update(p*2+1,mid+1,r,aim,value);
  180. 	}
  181. 	st[p].max=MAX(st[p*2].max,st[p*2+1].max);
  182.   }
  183. }
  184. int ask(int p,int lp,int rp,int la,int ra) //查询la,ra
  185. {
  186.   if (ra<la)
  187.     return 0;
  188.   if(lp==la && rp==ra)
  189.   {
  190.     return st[p].max;
  191.   } 
  192.   else 
  193.   {
  194.     int mid;
  195.     mid=(lp+rp)/2;
  196.     if (ra<=mid)
  197.     {
  198. 	  return ask(p*2,lp,mid,la,ra);
  199.     }
  200.     else if (mid<la)
  201.     {
  202. 	  return ask(p*2+1,mid+1,rp,la,ra);
  203. 	}
  204. 	else
  205. 	{
  206. 	  int t1=ask(p*2,lp,mid,la,mid);
  207. 	  int t2=ask(p*2+1,mid+1,rp,mid+1,ra);
  208. 	  return MAX(t1,t2);
  209. 	}
  210.   }
  211. } 
  212. void built_segment()
  213. {
  214.   REP(i,1,n-1)
  215.   {
  216.     if (T(in[i].x)deep>T(in[i].y)deep)//第一个点位父亲 
  217.     {
  218. 	  swap(in[i].x,in[i].y);
  219. 	}
  220. 	update(1,1,tot,T(in[i].y)w,in[i].cost);//更新x,y边的单点 直接改动权值 
  221.   }
  222. }
  223. void init()
  224. {
  225.   CLEAR(tree);
  226.   CLEAR(bian);
  227.   RI(n);
  228.   tot=T(root)deep=0;
  229.   T(root)w=++tot;
  230.   T(root)top=root;
  231.   REP(i,1,n-1)
  232.   {
  233.     RI(in[i].x);
  234.     RI(in[i].y);
  235.     RI(in[i].cost);
  236.     insert(in[i].x,in[i].y,in[i].cost);
  237.     insert(in[i].y,in[i].x,in[i].cost);
  238.   }
  239.   dfs(root); //预处理一些简单东西 
  240.   decomposition(root); //树链剖分
  241.   built_segment(); 
  242. }
  243. int find(int u,int v)//查询操作 
  244. {
  245.   int fu=T(u)top,fv=T(v)top;
  246.   int tmp=0;
  247.   while (fu!=fv) //不在同一条重链上
  248.   {
  249.     if (T(fu)deep<T(fv)deep) //只考虑f1比f2深的情况
  250. 	{
  251. 	  swap(fu,fv);
  252. 	  swap(u,v);
  253. 	} 
  254. 	tmp=MAX(tmp,ask(1,1,tot,T(fu)w,T(u)w)); //求解u->fu这条重链的最大边权
  255. 	//把u拉上来
  256. 	u=T(fu)fa; 
  257. 	fu=T(u)top;
  258.   } 
  259.   if (u==v) //拉到LCA上 
  260.   {
  261.     return tmp;
  262.   } 
  263.   if (T(u)deep>T(v)deep)
  264.   {
  265.     swap(u,v);
  266.   }
  267.   return MAX(tmp,ask(1,1,tot,T(T(u)son)w,T(v)w));//还有v-u这一段还没有查询过 
  268. }
  269. void work()
  270. {
  271.   char ch;
  272.   int a,b;
  273.   scanf("\n");
  274.   for (;1;)
  275.   {
  276.     ch=GCH();
  277. 	if ('Q'==ch)
  278.     {
  279.       GCH();
  280.       GCH();
  281.       GCH();
  282.       GCH();
  283.       RI(a);
  284.       RI(b);
  285. 	  scanf("\n");
  286. 	  printf("%d\n",find(a,b));
  287. 	}
  288. 	else if ('C'==ch)
  289. 	{
  290. 	  GCH();
  291.       GCH();
  292.       GCH();
  293.       GCH();
  294.       GCH();
  295.       RI(a);
  296.       RI(b);
  297. 	  scanf("\n");
  298. 	  update(1,1,tot,T(in[a].y)w,b);
  299. 	}
  300. 	else if ('D'==ch)
  301. 	{
  302. 	  GCH();
  303.       GCH();
  304.       GCH();
  305. 	  break;
  306. 	}
  307.   }
  308. }
  309. int main()
  310. {
  311.   int t;
  312.   open();
  313.   RI(t);
  314.   REP(i,1,t)
  315.   { 
  316.     init();
  317.     work();
  318.   }
  319.   close();
  320.   return 0;
  321. }
Time limit exceeded #stdin #stdout 5s 3684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NY2fZr
QTREE
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!