海淀网站建设价格,网络营销推广岗位有哪些,网页设计怎么把图片上移,访问网站 流程图题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid3966 树链剖分的模版#xff0c;成段更新单点查询。熟悉线段树的成段更新的话就小case啦。 1 //树链剖分 边权修改 单点查询2 #include iostream3 #include cstring4 #include algorithmhttp://acm.hdu.edu.cn/showproblem.php?pid3966 树链剖分的模版成段更新单点查询。熟悉线段树的成段更新的话就小case啦。 1 //树链剖分 边权修改 单点查询2 #include iostream3 #include cstring4 #include algorithm5 #include cstdio6 using namespace std;7 const int MAXN 5e4 10;8 struct data {9 int to , next;10 }edge[MAXN 1];11 int head[MAXN] , cnt , tot;12 int top[MAXN] , par[MAXN] , son[MAXN] , size[MAXN] , dep[MAXN];13 int id[MAXN] , fid[MAXN]; //id[i]表示i对应在线段树上的位置 fid[i]表示线段树位置是i的叶子 对应的节点 14 int a[MAXN];15 16 void init() {17 tot cnt 0;18 memset(head , -1 , sizeof(head));19 }20 21 inline void add(int u , int v) {22 edge[tot].next head[u];23 edge[tot].to v;24 head[u] tot;25 }26 27 void dfs1(int u , int p , int d) {28 dep[u] d , size[u] 1 , son[u] u , par[u] p;29 for(int i head[u] ; ~i ; i edge[i].next) {30 int v edge[i].to;31 if(v p)32 continue;33 dfs1(v , u , d 1);34 if(size[v] size[son[u]] || son[u] u)35 son[u] v;36 size[u] size[v];37 }38 }39 40 void dfs2(int u , int p , int t) {41 top[u] t , id[u] cnt;42 fid[cnt] u;43 if(son[u] ! u)44 dfs2(son[u] , u , t);45 for(int i head[u] ; ~i ; i edge[i].next) {46 int v edge[i].to;47 if(v p || v son[u])48 continue;49 dfs2(v , u , v);50 }51 }52 53 struct segtree {54 int l , r;55 int sum;56 }T[MAXN 2];57 58 void pushup(int p) {59 if(T[p].sum ! 0) {60 int ls p 1 , rs (p 1)|1;61 T[ls].sum T[p].sum;62 T[rs].sum T[p].sum;63 T[p].sum 0;64 }65 }66 67 void build(int p , int l , int r) {68 int mid (l r) 1;69 T[p].l l , T[p].r r;70 T[p].sum 0;71 if(l r) {72 T[p].sum a[fid[l]]; //73 return ;74 }75 build(p 1 , l , mid);76 build((p 1)|1 , mid 1 , r);77 }78 79 void updata(int p , int l , int r , int num) {80 int mid (T[p].l T[p].r) 1;81 if(T[p].l l T[p].r r) {82 T[p].sum num;83 return ;84 }85 pushup(p);86 if(r mid) {87 updata(p 1 , l , r , num);88 }89 else if(l mid) {90 updata((p 1)|1 , l , r , num);91 }92 else {93 updata(p 1 , l , mid , num);94 updata((p 1)|1 , mid 1 , r , num);95 }96 }97 98 int query(int p , int pos) {99 int mid (T[p].l T[p].r) 1;
100 if(T[p].l T[p].r T[p].r pos) {
101 return T[p].sum;
102 }
103 pushup(p);
104 if(pos mid) {
105 return query(p 1 , pos);
106 }
107 else {
108 return query((p 1)|1 , pos);
109 }
110 }
111
112 void change(int u , int v , int num) {
113 int fu top[u] , fv top[v];
114 int sum 0;
115 while(fu ! fv) {
116 if(dep[fu] dep[fv]) {
117 updata(1 , id[fu] , id[u] , num);
118 u par[fu];
119 fu top[u];
120 }
121 else {
122 updata(1 , id[fv] , id[v] , num);
123 v par[fv];
124 fv top[v];
125 }
126 }
127 if(dep[u] dep[v]) {
128 updata(1 , id[v] , id[u] , num);
129 }
130 else {
131 updata(1 , id[u] , id[v] , num);
132 }
133 }
134
135 int main()
136 {
137 int n , u , v , m , xx;
138 while(~scanf(%d %d %d , n , xx , m)) {
139 init();
140 for(int i 1 ; i n ; i) {
141 scanf(%d , a i);
142 }
143 for(int i 1 ; i n ; i) {
144 scanf(%d %d , u , v);
145 add(u , v);
146 add(v , u);
147 }
148 cnt 0;
149 dfs1(1 , 1 , 0);
150 dfs2(1 , 1 , 1);
151 build(1 , 1 , cnt);
152 char q[10];
153 while(m--) {
154 scanf(%s , q);
155 if(q[0] Q) {
156 scanf(%d , xx);
157 printf(%d\n , query(1 , id[xx]));
158 }
159 else if(q[0] I) {
160 scanf(%d %d %d , u , v , xx);
161 change(u , v , xx);
162 }
163 else {
164 scanf(%d %d %d , u , v , xx);
165 change(u , v , -xx);
166 }
167 }
168 }
169 return 0;
170 } 转载于:https://www.cnblogs.com/Recoder/p/5518179.html
