# 树链剖分简单分析及模板(杂谈)

```  1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5 using namespace std;
6 #define Del(a,b) memset(a,b,sizeof(a))
7 const int N = 10005;
8
9 int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N]; //top 最近的重链父节点
10 int num;
11 vector<int> v[N];
12 struct tree
13 {
14     int x,y,val;
16         scanf("%d%d%d",&x,&y,&val);
17     }
18 };
19 tree e[N];
20 void dfs1(int u, int f, int d) {
21     dep[u] = d;
22     siz[u] = 1;
23     son[u] = 0;
24     fa[u] = f;
25     for (int i = 0; i < v[u].size(); i++) {
26         int ff = v[u][i];
27         if (ff == f) continue;
28         dfs1(ff, u, d + 1);
29         siz[u] += siz[ff];
30         if (siz[son[u]] < siz[ff])
31             son[u] = ff;
32     }
33 }
34 void dfs2(int u, int tp) {
35     top[u] = tp;
36     id[u] = ++num;
37     if (son[u]) dfs2(son[u], tp);
38     for (int i = 0; i < v[u].size(); i++) {
39         int ff = v[u][i];
40         if (ff == fa[u] || ff == son[u]) continue;
41         dfs2(ff, ff);
42     }
43 }
44 #define lson(x) ((x<<1))
45 #define rson(x) ((x<<1)+1)
46 struct Tree
47 {
48     int l,r,val;
49 };
50 Tree tree[4*N];
51 void pushup(int x) {
52     tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);
53 }
54
55 void build(int l,int r,int v)
56 {
57     tree[v].l=l;
58     tree[v].r=r;
59     if(l==r)
60     {
61         tree[v].val = val[l];
62         return ;
63     }
64     int mid=(l+r)>>1;
65     build(l,mid,v*2);
66     build(mid+1,r,v*2+1);
67     pushup(v);
68 }
69 void update(int o,int v,int val)  //log(n)
70 {
71     if(tree[o].l==tree[o].r)
72     {
73         tree[o].val = val;
74         return ;
75     }
76     int mid = (tree[o].l+tree[o].r)/2;
77     if(v<=mid)
78         update(o*2,v,val);
79     else
80         update(o*2+1,v,val);
81     pushup(o);
82 }
83 int query(int x,int l, int r)
84 {
85     if (tree[x].l >= l && tree[x].r <= r) {
86         return tree[x].val;
87     }
88     int mid = (tree[x].l + tree[x].r) / 2;
89     int ans = 0;
90     if (l <= mid) ans = max(ans, query(lson(x),l,r));
91     if (r > mid) ans = max(ans, query(rson(x),l,r));
92     return ans;
93 }
94
95 int Yougth(int u, int v) {
96     int tp1 = top[u], tp2 = top[v];
97     int ans = 0;
98     while (tp1 != tp2) {
99         //printf("YES\n");
100         if (dep[tp1] < dep[tp2]) {
101             swap(tp1, tp2);
102             swap(u, v);
103         }
104         ans = max(query(1,id[tp1], id[u]), ans);
105         u = fa[tp1];
106         tp1 = top[u];
107     }
108     if (u == v) return ans;
109     if (dep[u] > dep[v]) swap(u, v);
110     ans = max(query(1,id[son[u]], id[v]), ans);
111     return ans;
112 }
113 void Clear(int n)
114 {
115     for(int i=1;i<=n;i++)
116         v[i].clear();
117 }
118 int main()
119 {
120     //freopen("Input.txt","r",stdin);
121     int T;
122     scanf("%d",&T);
123     while(T--)
124     {
125         int n;
126         scanf("%d",&n);
127         for(int i=1;i<n;i++)
128         {
130             v[e[i].x].push_back(e[i].y);
131             v[e[i].y].push_back(e[i].x);
132         }
133         num = 0;
134         dfs1(1,0,1);
135         dfs2(1,1);
136         for (int i = 1; i < n; i++) {
137             if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x, e[i].y);
138             val[id[e[i].x]] = e[i].val;
139         }
140         build(1,num,1);
141         char s[200];
142         while(~scanf("%s",&s) && s[0]!='D')
143         {
144             int x,y;
145             scanf("%d%d",&x,&y);
146             if(s[0]=='Q')
147                 printf("%d\n",Yougth(x,y));
148             if (s[0] == 'C')
149                 update(1,id[e[x].x],y);
150         }
151         Clear(n);
152     }
153     return 0;
154 }```

0 条评论

## 相关文章

3497

2455

1758

1152

44611

### 实验4　类初步

注：本次实验有可能会安排在校内http://acm.hpu.edu.cn/contest.php进行。

872

### [LeetCode] 120. Triangle

【原题】 Given a triangle, find the minimum path sum from top to bottom. Each step...

1987

4784

3666

3548