這是樹鏈剖分的入門題，也是我學樹鏈剖分的第一題。

樹鏈剖分：就是把樹中和線段樹聯系起來，求（u，v）路徑中權值的最大值和其路徑的權值和。

入門blog:http://blog.sina.com.cn/s/blog_7a1746820100wp67.html?

? ? ? ? ? ?https://quartergeek.com/summary-of-heavy-light-decomposition/

kuangbin 菊苣的專題訓練：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28982#overview

我的第一樹鏈

#include<bits/stdc++.h> using namespace std; #define N 30010struct Edge {int to,next; }edge[N*2];int head[N],tot; int top[N],fa[N],deep[N],num[N],p[N],fp[N],son[N],pos;void init() {tot=0;memset(head,-1,sizeof(head));pos=0;memset(son,-1,sizeof(son)); }void addedge(int u,int v) {edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++; }void dfs1(int u,int pre,int d) {deep[u]=d;fa[u]=pre;num[u]=1;for (int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if (v!=pre){dfs1(v,u,d+1);num[u]+=num[v];if (son[u]==-1||num[v]>num[son[u]])son[u]=v;}} }void getpos(int u,int sp) {top[u]=sp;p[u]=pos++;fp[p[u]]=u;if (son[u]==-1) return;getpos(son[u],sp);for (int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if (v!=son[u]&&v!=fa[u]) getpos(v,v);} } struct node {int l,r;int sum;int Max; }tree[N*3]; void push_up(int i) {tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;tree[i].Max=max(tree[i<<1].Max,tree[i<<1|1].Max); } int s[N];void build(int i,int l,int r) {tree[i].l=l;tree[i].r=r;if (l==r){tree[i].sum=tree[i].Max=s[fp[l]];return;}int mid=(l+r)>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);push_up(i); } void update(int i,int k,int val) {if (tree[i].l==k&&tree[i].r==k){tree[i].sum=tree[i].Max=val;return;}int mid=(tree[i].l+tree[i].r)/2;if (k<=mid) update(i<<1,k,val);else update(i<<1|1,k,val);push_up(i); }int query_max(int i,int l,int r) {if (tree[i].l==l&&tree[i].r==r)return tree[i].Max;int mid=(tree[i].l+tree[i].r)/2;if (r<=mid) return query_max(i<<1,l,r);else if (l>mid) return query_max(i<<1|1,l,r);else return max(query_max(i<<1,l,mid),query_max(i<<1|1,mid+1,r)); }int query_sum(int i,int l,int r) {if (tree[i].l==l&&tree[i].r==r)return tree[i].sum;int mid=(tree[i].l+tree[i].r)/2;if (r<=mid) return query_sum(i<<1,l,r);else if (l>mid) return query_sum(i<<1|1,l,r);else return query_sum(i<<1,l,mid)+query_sum(i<<1|1,mid+1,r); }int findmax(int u,int v) {int f1=top[u],f2=top[v];int tmp=-12345667;while (f1!=f2){if (deep[f1]<deep[f2]){swap(f1,f2);swap(u,v);}tmp=max(tmp,query_max(1,p[f1],p[u]));u=fa[f1];f1=top[u];}if (deep[u]>deep[v]) swap(u,v);return max(tmp,query_max(1,p[u],p[v])); }int findsum(int u,int v) {int f1=top[u],f2=top[v];int tmp=0;while (f1!=f2){if (deep[f1]<deep[f2]){swap(f1,f2);swap(u,v);}tmp+=query_sum(1,p[f1],p[u]);u=fa[f1];f1=top[u];}if (deep[u]>deep[v]) swap(u,v);return tmp+query_sum(1,p[u],p[v]); }int main() {int n;int q;char op[20];int u,v;while(scanf("%d",&n) == 1){init();for(int i = 1;i < n;i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}for(int i = 1;i <= n;i++)scanf("%d",&s[i]);dfs1(1,0,0);getpos(1,1);build(1,0,pos-1);scanf("%d",&q);while(q--){scanf("%s%d%d",op,&u,&v);if(op[0] == 'C')update(1,p[u],v);//修改單點的值else if(strcmp(op,"QMAX") == 0)printf("%d\n",findmax(u,v));//查詢u->v路徑上點權的最大值else printf("%d\n",findsum(u,v));//查詢路徑上點權的和 }}return 0; }

?

份代碼：

轉載于:https://www.cnblogs.com/forgot93/p/4105573.html

總結

以上是生活随笔為你收集整理的树链剖分 - BZOJ 1036: [ZJOI2008]树的统计Count的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。