一棵树上有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本身,
树链剖分裸题
树链剖分就是将树剖成重链和轻链,然后按重儿子优先的dfs序建线段树,然后遇到查询时,只需在树上暴跳即可,每次将深度大的点跳到这条链的顶端,直到顶端相同(本质还是dfs序线段树,只是建树方式不太一样便可维护链上的信息,)复杂度O(nlognlogn),树上暴跳复杂度是O(logn),因为当树退化时跳的越远,所以复杂度logn
/**************************************************************Problem: 1036User: walfyLanguage: C++Result: AcceptedTime:2524 msMemory:5552 kb ****************************************************************///#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=30000+10,maxn=60000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;struct edge{int to,Next; }e[maxn]; int cnt,head[N]; int son[N],fa[N],top[N],sz[N],id[N]; int res,w[N],re[N],dep[N]; void add(int u,int v) {e[cnt].to=v;e[cnt].Next=head[u];head[u]=cnt++; } void init() {cnt=0;memset(head,-1,sizeof head);memset(son,-1,sizeof son); } void dfs1(int u,int f,int de) {fa[u]=f;sz[u]=1;dep[u]=de;for(int i=head[u];~i;i=e[i].Next){int v=e[i].to;if(v!=f){dfs1(v,u,de+1);sz[u]+=sz[v];if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;}} } void dfs2(int u,int f,int tp) {top[u]=tp;id[u]=++res;if(son[u]!=-1)dfs2(son[u],u,tp);for(int i=head[u];~i;i=e[i].Next){int v=e[i].to;if(v!=f&&v!=son[u])dfs2(v,u,v);} } int sum[N<<2],ma[N<<2]; void pushup(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1];ma[rt]=max(ma[rt<<1],ma[rt<<1|1]); } void build(int l,int r,int rt) {if(l==r){sum[rt]=ma[rt]=w[re[l]];return ;}int m=(l+r)>>1;build(ls);build(rs);pushup(rt); } void update(int x,int c,int l,int r,int rt) {if(l==r){sum[rt]=ma[rt]=c;return ;}int m=(l+r)>>1;if(x<=m)update(x,c,ls);else update(x,c,rs);pushup(rt); } int queryma(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return ma[rt];int m=(l+r)>>1,ans=-1e9;if(L<=m)ans=max(ans,queryma(L,R,ls));if(m<R)ans=max(ans,queryma(L,R,rs));return ans; } int querysum(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return sum[rt];int m=(l+r)>>1,ans=0;if(L<=m)ans+=querysum(L,R,ls);if(m<R)ans+=querysum(L,R,rs);return ans; } int query(int op,int a,int b) {int f1=top[a],f2=top[b],ans=0;if(op==0)ans=-1e9;while(f1!=f2){if(dep[f1]<dep[f2])swap(f1,f2),swap(a,b);if(op==0)ans=max(ans,queryma(id[f1],id[a],1,res,1));else ans+=querysum(id[f1],id[a],1,res,1);a=fa[f1];f1=top[a];}if(dep[a]>dep[b])swap(a,b);if(op==0)ans=max(ans,queryma(id[a],id[b],1,res,1));else ans+=querysum(id[a],id[b],1,res,1);return ans; } int main() {int n;scanf("%d",&n);init();for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a);}for(int i=1;i<=n;i++)scanf("%d",&w[i]);dfs1(1,-1,1);dfs2(1,-1,1);for(int i=1;i<=res;i++)re[id[i]]=i;build(1,res,1);int q;scanf("%d",&q);while(q--){char op[10];int a,b;scanf("%s%d%d",op,&a,&b);if(op[1]=='M')printf("%d\n",query(0,a,b));else if(op[1]=='S')printf("%d\n",query(1,a,b));else update(id[a],b,1,res,1);}return 0; } /*********************** 8 1 2 1 7 2 3 2 4 4 5 4 6 7 8 ***********************/
