本文主要是介绍洛谷 P2590 [ZJOI2008]树的统计(树链剖分+线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
输入输出格式
输入格式：
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式：
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
题解:树链剖分的模板题,第一遍dfs确认轻重孩子,第二遍dfs拉出轻重链,每一条轻重链便成了一条条的序列,然后用线段树维护区间最大值和区间和即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1int _dfs[maxn],son[maxn],far[maxn],siz[maxn],sum[maxn];
int dep[maxn],tot,top[maxn],n,a[maxn],id[maxn],tree[maxn];
vector<int>G[maxn];void dfs1(int u,int fa,int depth)
{far[u]=fa;siz[u]=1;dep[u]=depth;int sz=G[u].size();for(int i=0;i<sz;i++){int v=G[u][i];if(v==fa) continue;dfs1(v,u,depth+1);siz[u]+=siz[v];if(siz[v]>siz[son[u]]) son[u]=v;}
}void dfs2(int x,int t)
{_dfs[x]=++tot;top[x]=t;id[tot]=x;if(son[x]) dfs2(son[x],t);int sz=G[x].size();for(int i=0;i<sz;i++){int v=G[x][i];if(v!=far[x] && v!=son[x])dfs2(v,v);}
}void build(int l=1,int r=n,int rt=1)
{if(l==r){tree[rt]=a[id[l]];sum[rt]=a[id[l]];return;}int m=(l+r)>>1;build(lson);build(rson);sum[rt]=sum[rt<<1]+sum[rt<<1|1];tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}int querys(int L,int R,int l=1,int r=n,int rt=1)
{if(l>=L && r<=R) return sum[rt];int m=(l+r)>>1,ans=0;if(L<=m) ans+=querys(L,R,lson);if(R>m) ans+=querys(L,R,rson);return ans;
}int querym(int L,int R,int l=1,int r=n,int rt=1)
{if(l>=L && r<=R) return tree[rt];int m=(l+r)>>1,ans=-0x3f3f3f3f;if(L<=m) ans=max(ans,querym(L,R,lson));if(R>m) ans=max(ans,querym(L,R,rson));return ans;
}void update(int o,int v,int l=1,int r=n,int rt=1)
{if(l==r){tree[rt]=sum[rt]=v;return;}int m=(l+r)>>1;if(o<=m) update(o,v,lson);else update(o,v,rson);sum[rt]=sum[rt<<1]+sum[rt<<1|1];tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}int calm(int u,int v)
{int ans=-0x3f3f3f3f;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);ans=max(ans,querym(_dfs[top[u]],_dfs[u]));u=far[top[u]];}if(dep[u]>dep[v])swap(u,v);ans=max(ans,querym(_dfs[u],_dfs[v]));return ans;
}int cals(int u,int v)
{int ans=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);ans+=querys(_dfs[top[u]],_dfs[u]);u=far[top[u]];}if(dep[u]>dep[v])swap(u,v);ans+=querys(_dfs[u],_dfs[v]);return ans;
}int main()
{scanf("%d",&n);for(int i=0;i<n-1;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=n;i++)scanf("%d",&a[i]);dfs1(1,1,0);dfs2(1,1);build();int q;scanf("%d",&q);while(q--){char s[15]={0};scanf("%s",s);int u,v;scanf("%d%d",&u,&v);if(s[0]=='C')update(_dfs[u],v);else if(s[1]=='M'){int ans=calm(u,v);printf("%d\n",ans);}else{int ans=cals(u,v);printf("%d\n",ans);}}return 0;
}
这篇关于洛谷 P2590 [ZJOI2008]树的统计(树链剖分+线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
