标签：solution clear struct span || oid style stdio.h under
1 /**
2 problem: http://poj.org/problem?id=2763
3 **/
4 #include 5 #include 6 #includestring.h>
7 #include 8 using namespace std;
9
10 const int MAXN = 100005;
11
12 template 13 class SegmentTree {
14 private:
15 struct Node {
16 int left, right;
17 T sum, lazy;
18 } node[MAXN 2];
19 T data[MAXN];
20 void pushUp(int root) {
21 node[root].sum = node[root 1].sum + node[root 1 | 1].sum;
22 }
23 void pushDown(int root) {
24 if(node[root].left == node[root].right) return;
25 int lson = root 1;
26 int rson = root 1 | 1;
27 node[lson].sum = node[root].lazy * (node[lson].right - node[lson].left + 1);
28 node[rson].sum = node[root].lazy * (node[rson].right - node[rson].left + 1);
29 node[lson].lazy = node[root].lazy;
30 node[rson].lazy = node[root].lazy;
31 node[root].lazy = 0;
32 }
33 public:
34 void build(int left, int right, int root = 1) {
35 node[root].left = left;
36 node[root].right = right;
37 node[root].lazy = 0;
38 if(left == right) {
39 node[root].sum = data[left];
40 } else {
41 int mid = (left + right) >> 1;
42 build(left, mid, root 1);
43 build(mid + 1, right, root 1 | 1);
44 pushUp(root);
45 }
46 }
47 void update(int left, int right, T value, int root = 1) {
48 int lson = root 1;
49 int rson = root 1 | 1;
50 if(node[root].lazy) pushDown(root);
51 if(node[root].left == left && node[root].right == right) {
52 node[root].sum = value * (right - left + 1);
53 node[root].lazy = value;
54 return ;
55 }
56 if(left >= node[rson].left) {
57 update(left, right, value, rson);
58 } else if(right node[lson].right) {
59 update(left, right, value, lson);
60 } else {
61 update(left, node[lson].right, value, lson);
62 update(node[rson].left, right, value, rson);
63 }
64 pushUp(root);
65 }
66 T query(int left, int right, int root = 1) {
67 int lson = root 1;
68 int rson = root 1 | 1;
69 if(node[root].lazy) pushDown(root);
70 if(node[root].left == left && node[root].right == right) {
71 return node[root].sum;
72 }
73 if(left >= node[rson].left) {
74 return query(left, right, rson);
75 } else if(right node[lson].right) {
76 return query(left, right, lson);
77 } else {
78 return query(left, node[lson].right, lson) + query(node[rson].left, right, rson);
79 }
80 }
81 void clear(int n, const vectorint> &d) {
82 for(int i = 1; i ) {
83 this->data[i] = d[i];
84 }
85 build(1, n);
86 }
87 };
88
89 template 90 class TreeToLink {
91 private:
92 struct Point {
93 int size, son, depth, father, top, newId;
94 T data;
95 } point[MAXN];
96 struct Edge {
97 int to, next;
98 } edge[MAXN 1];
99 int oldId[MAXN], first[MAXN], sign, sumOfPoint, cnt;
100 SegmentTree st;
101 void dfs1(int u, int father = 0, int depth = 1) {
102 point[u].depth = depth;
103 point[u].father = father;
104 point[u].size = 1;
105 int maxson = -1;
106 for(int i = first[u]; i != -1; i = edge[i].next) {
107 int to = edge[i].to;
108 if(to == father) continue;
109 dfs1(to, u, depth + 1);
110 point[u].size += point[to].size;
111 if(point[to].size > maxson) {
112 point[u].son = to;
113 maxson = point[to].size;
114 }
115 }
116 }
117 void dfs2(int u, int top) {
118 point[u].newId = ++cnt;
119 oldId[cnt] = u;
120 point[u].top = top;
121 if(point[u].son == -1) {
122 return ;
123 }
124 dfs2(point[u].son, top);
125 for(int i = first[u]; i != -1; i = edge[i].next) {
126 int to = edge[i].to;
127 if(to == point[u].son || to == point[u].father) continue;
128 dfs2(to, to);
129 }
130 }
131 public:
132 void clear(int n) {
133 sumOfPoint = n;
134 sign = 0;
135 cnt = 0;
136 for(int i = 1; i ) {
137 first[i] = -1;
138 point[i].son = -1;
139 // scanf("%d", &point[i].data); // input
140 point[i].data = 0;
141 }
142 }
143 void addEdgeOneWay(int u, int v) {
144 edge[sign].to = v;
145 edge[sign].next = first[u];
146 first[u] = sign ++;
147 }
148 void addEdgeTwoWay(int u, int v) {
149 addEdgeOneWay(u, v);
150 addEdgeOneWay(v, u);
151 }
152 void preWork(int x = 1) {
153 dfs1(x);
154 dfs2(x, x);
155 vectorint> data(sumOfPoint + 1);
156 for(int i = 1; i ) {
157 data[i] = point[oldId[i]].data;
158 }
159 st.clear(sumOfPoint, data);
160 }
161 void updatePath(int x, int y, T z){
162 while(point[x].top != point[y].top){
163 if(point[point[x].top].depth point[point[y].top].depth)
164 swap(x, y);
165 st.update(point[point[x].top].newId, point[x].newId, z);
166 x = point[point[x].top].father;
167 }
168 if(point[x].depth > point[y].depth)
169 swap(x, y);
170 st.update(point[x].newId, point[y].newId, z);
171 }
172 T queryPath(int x, int y){
173 T ans = 0;
174 while(point[x].top != point[y].top){
175 if(point[point[x].top].depth point[point[y].top].depth)
176 swap(x, y);
177 ans += st.query(point[point[x].top].newId, point[x].newId);
178 x = point[point[x].top].father;
179 }
180 if(x == y) return ans; // Edge
181 if(point[x].depth > point[y].depth)
182 swap(x, y);
183 // ans += st.query(point[x].newId, point[y].newId); // Point
184 ans += st.query(point[point[x].son].newId, point[y].newId); // Edge
185 return ans;
186 }
187 void updateSon(int x, T z){
188 st.update(point[x].newId, point[x].newId + point[x].size - 1, z);
189 }
190 T querySon(int x){
191 return st.query(point[x].newId, point[x].newId + point[x].size - 1);
192 }
193 T queryPoint(int x) {
194 return queryPath(x, x);
195 }
196 void updatePoint(int x, T z) {
197 updatePath(x, x, z);
198 }
199 bool deeper(int u, int v){
200 return point[u].depth > point[v].depth;
201 }
202 };
203
204 class Solution {
205 private:
206 int n, q, s;
207 TreeToLinkint> ttl;
208 struct Edge{
209 int u, v, w;
210 }edge[MAXN];
211 public:
212 void solve() {
213 scanf("%d%d%d", &n, &q, &s);
214 ttl.clear(n);
215 for(int i = 1; i ){
216 scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
217 ttl.addEdgeTwoWay(edge[i].u, edge[i].v);
218 }
219 ttl.preWork(s);
220 for(int i = 1; i ){
221 if(ttl.deeper(edge[i].u, edge[i].v)){
222 swap(edge[i].u, edge[i].v);
223 }
224 ttl.updatePoint(edge[i].v, edge[i].w);
225 }
226 int now = s;
227 for(int i = 0, a, b, c; i ){
228 scanf("%d%d", &a, &b);
229 if(a == 1){
230 scanf("%d", &c);
231 ttl.updatePoint(edge[b].v, c);
232 }else{
233 printf("%d\n", ttl.queryPath(now, b));
234 now = b;
235 }
236 }
237 }
238 } DarkScoCu;
239
240 int main() {
241 DarkScoCu.solve();
242 return 0;
243 }
poj 2763 Housewife Wind : 树链剖分维护边 O(nlogn)建树 O((logn)²)修改与查询
标签：solution clear struct span || oid style stdio.h under
原文地址：https://www.cnblogs.com/DarkScoCu/p/10699152.html