树链剖分-入门题目

Query on a tree

题目链接: http://vjudge.net/problem/SPOJ-QTREE

题目大致意思就是: 给你一棵树,有连个操作:

● 第一个是查询任意两个不同节点上的最短路径上的最大权边!

● 第二个操作修改某一条边的权值;

对于一棵树,数的深度如果很大,那么每次查询两个叶子节点,时间复杂度还是很高的。所以我们就把树分成一条一条的树链，所谓树链就是：沿着树的一条路径。得到路径后，我们可以用堆，线段树进行维护。在一些题目中，树链剖分题目，一般可以用dfs 进行剖链。

鄙人学习树链剖分所用到资料：

ACdreams 大神博客，看这篇博客主要知道什么是树链剖分，以及原理；知道树链剖分部分，剖分树链之后需要用一些数据结构维护，大部分用线段树。线段树比较常用。所以我也用线段树；

如果觉得博客看着费劲，还是不知道原理是什么的话，可以尝试看看 UESTCACM 每周算法讲堂 dfs序与树链剖分

有了以上知识储备，做这个题目也比较轻松！线段树要会！！可以参考kuangbin题解来做；附上我AC代码，一是为了存个模板，二还请大佬指出错误！

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cctype>
  4 #include<cmath>
  5 #include<set>
  6 #include<map>
  7 #include<list>
  8 #include<queue>
  9 #include<deque>
 10 #include<stack>
 11 #include<string>
 12 #include<vector>
 13 #include<iostream>
 14 #include<algorithm>
 15 #include<stdlib.h>
 16 #include<time.h>
 17 
 18 using namespace std;
 19 typedef long long LL;
 20 const int INF=2e9+1e8;
 21 const int MOD=1e9+7;
 22 const int MAXSIZE=2e4+100;
 23 const double eps=0.0000000001;
 24 void fre()
 25 {
 26     freopen("in.txt","r",stdin);
 27     freopen("out.txt","w",stdout);
 28 }
 29 #define memst(a,b) memset(a,b,sizeof(a))
 30 #define fr(i,a,n) for(int i=a;i<n;i++)
 31 
 32 int son[MAXSIZE],deep[MAXSIZE],father[MAXSIZE],num[MAXSIZE],top[MAXSIZE],p[MAXSIZE],fp[MAXSIZE],pos;
 33 int Treevalue[MAXSIZE];
 34 // son 代表重儿子; deep 深度;father 父亲节点;num 统计节点个数;
 35 //top 树链的头, p 某个节点在线段树的位置 ; fp 线段树某个位置在树中的位置;
 36 //pos 是用来对树的节点进行标号的;
 37 
 38 // 建图部分
 39 int first[MAXSIZE],ntot;
 40 struct  Node
 41 {
 42     int to,next,val;
 43 };
 44 struct NODE
 45 {
 46     int a,b,c;
 47 } input[MAXSIZE];
 48 Node edge[MAXSIZE];
 49 void init()
 50 {
 51     memst(first,-1);
 52     memst(son,-1);
 53     pos=ntot=0;
 54 }
 55 void addedge(int s,int t,int val)
 56 {
 57     edge[ntot].to=t,edge[ntot].val=val;
 58     edge[ntot].next=first[s],first[s]=ntot++;
 59 }
 60 // 剖分树链
 61 void dfs(int x,int pre,int _deep)
 62 {
 63     deep[x]=_deep;
 64     father[x]=pre;
 65     num[x]=1;
 66     for(int i=first[x]; i!=-1; i=edge[i].next)
 67     {
 68         int to=edge[i].to;
 69         if(to!=pre)
 70         {
 71             Treevalue[to]=edge[i].val;
 72             dfs(to,x,_deep+1);
 73             num[x]+=num[to];
 74             if(son[x]==-1||num[to]>num[son[x]]) son[x]=to;
 75         }
 76     }
 77     return ;
 78 }
 79 void getlist(int x,int pr)
 80 {
 81     top[x]=pr;
 82     if(son[x]!=-1) // 如果存在重儿子,就沿着一直找下去
 83     {
 84         p[x]=pos++;
 85         fp[p[x]]=x;
 86         getlist(son[x],pr);
 87     }
 88     else //直到到低端为止
 89     {
 90         p[x]=pos++;
 91         fp[p[x]]=x;
 92         return ;
 93     }
 94     for(int i=first[x]; i!=-1; i=edge[i].next)
 95     {
 96         int to=edge[i].to;
 97         if(to!=son[x]&&to!=father[x]) getlist(to,to); //如果不是往回走 且 不是重儿子那么就是新的树链进行dfs金合欢花;
 98     }
 99 }
100 //树链剖分部分 完成
101 
102 // 线段树部分
103 struct TreeNode
104 {
105     int l,r,max;
106 } tree[MAXSIZE*3];
107 void push_up(int i)
108 {
109     tree[i].max=max(tree[i<<1].max,tree[i<<1|1].max);
110 }
111 void build(int i,int l,int r)
112 {
113     tree[i].l=l,tree[i].r=r,tree[i].max=0;
114     if(l==r)
115     {
116         tree[i].max=Treevalue[fp[l]];
117         return ;
118     }
119     int mid=(l+r)>>1;
120     build(i<<1,l,mid);
121     build(i<<1|1,mid+1,r);
122     push_up(i);
123 }
124 int query(int i,int l,int r)
125 {
126     if(tree[i].l==l&&tree[i].r==r) return tree[i].max;
127     int mid=(tree[i].l+tree[i].r)>>1;
128     if(l>mid) return query(i<<1|1,l,r);
129     else if(r<=mid) return query(i<<1,l,r);
130     else return max(query(i<<1|1,mid+1,r),query(i<<1,l,mid));
131 }
132 int getmax(int a,int b)
133 {
134     int res=0;
135     int f1=top[a],f2=top[b];
136     while(f1!=f2)
137     {
138         if(deep[f1]>deep[f2])
139         {
140             res=max(res,query(1,p[f1],p[a]));
141             a=father[f1],f1=top[a];
142         }
143         else
144         {
145             res=max(res,query(1,p[f2],p[b]));
146             b=father[f2],f2=top[b];
147         }
148     }
149     if(a==b) return res;
150     if(deep[a]>deep[b]) swap(a,b);
151     return max(res,query(1,p[son[a]],p[b]));
152 }
153 
154 void update(int i,int k,int val)//插点
155 {
156     if(tree[i].l==k&&tree[i].r==k)
157     {
158         tree[i].max=val;
159         return ;
160     }
161     int mid=(tree[i].l+tree[i].r)>>1;
162     if(k>mid) update(i<<1|1,k,val);
163     else update(i<<1,k,val);
164     push_up(i);
165 }
166 void Debug(int i,int l,int r)
167 {
168     if(tree[i].r>r||tree[i].l<l) return ;
169     printf("i=%d l=%d r=%d max=%d
",i,tree[i].l,tree[i].r,tree[i].max);
170     Debug(i<<1,l,r);
171     Debug(i<<1|1,l,r);
172 }
173 int main()
174 {
175     int ncase,n;
176     scanf("%d",&ncase);
177     while(ncase--)
178     {
179         init();
180         scanf("%d",&n);
181         for(int i=1; i<n; i++)
182         {
183             scanf("%d%d%d",&input[i].a,&input[i].b,&input[i].c);
184             addedge(input[i].a,input[i].b,input[i].c);
185             addedge(input[i].b,input[i].a,input[i].c);
186         }
187         dfs(1,0,0);//把图变成一棵树;
188         getlist(1,1);//剖树链;
189         build(1,1,n-1);
190         while(1)
191         {
192             char opt[10];
193 
194             scanf("%s",opt);
195             if(opt[0]=='D') break;
196             if(opt[0]=='C')
197             {
198                 int change_pos,value;
199                 scanf("%d%d",&change_pos,&value);
200                 int a=input[change_pos].a,b=input[change_pos].b;
201                 if(deep[a]>deep[b]) swap(a,b);
202                 update(1,p[b],value);
203             }
204             else
205             {
206                 int a,b;
207                 scanf("%d%d",&a,&b);
208                 printf("%d
",getmax(a,b));
209             }
210         }
211     }
212     return 0;
213 }
214 /**************************************************/
215 /**             Copyright Notice                 **/
216 /**  writer: wurong                              **/
217 /**  school: nyist                               **/
218 /**  blog  : http://blog.csdn.net/wr_technology  **/
219 /**************************************************/