P2590 [ZJOI2008]樹的統(tǒng)計

?

I. CHANGE u t : 把結(jié)點u的權(quán)值改為t

II. QMAX u v: 詢問從點u到點v的路徑上的節(jié)點的最大權(quán)值

III. QSUM u v: 詢問從點u到點v的路徑上的節(jié)點的權(quán)值和

?

（博主）神蒟本蒻，又A了一道樹鏈剖分的模板題，還是太頹廢了。。。

調(diào)了我一個小時。。。

dfs+線段樹維護區(qū)間和和最大值。

自帶大常常數(shù)

#include<iostream> #include<cstdio> #include<cmath>#define LL long long #define IL inline #define RE register #define N 1000000 using namespace std;int head[N],tot,n,m,val[N],val_w[N]; struct node{int to,next; }e[N];void add(int u,int v){e[++tot].to=v,e[tot].next=head[u],head[u]=tot; }int f[N],siz[N],son[N],top[N],dep[N],id[N],item;IL void dfs1(int u,int fa){f[u]=fa,siz[u]=1,dep[u]=dep[fa]+1;int maxson=-1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>maxson) maxson=siz[v],son[u]=v;} }IL void dfs2(int u,int topf){id[u]=++item,top[u]=topf,val_w[item]=val[u];if(!son[u]) return;dfs2(son[u],topf);for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==f[u]||v==son[u]) continue;dfs2(v,v);} } struct Segment{int l,r,w,w_max; }tr[N];IL void push_up(int k){tr[k].w_max=max(tr[k<<1].w_max,tr[k<<1|1].w_max);tr[k].w=tr[k<<1].w+tr[k<<1|1].w; }IL void build(int k,int l,int r){tr[k].l=l,tr[k].r=r;if(l==r){tr[k].w=tr[k].w_max=val_w[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);push_up(k); }IL void change(int k,int X,int val_V){int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if(l==r) {tr[k].w_max=tr[k].w=val_V;return;}if(X<=mid) change(k<<1,X,val_V);else change(k<<1|1,X,val_V);push_up(k); }IL int ask_max(int k,int ql,int qr){int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if(l>=ql&&r<=qr) return tr[k].w_max;int ans=-0x7fffffff;if(ql<=mid) ans=ask_max(k<<1,ql,qr);if(qr>mid) ans=max(ans,ask_max(k<<1|1,ql,qr));return ans; }IL int ask_sum(int k,int ql,int qr){int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if(l>=ql&&r<=qr) return tr[k].w;int ans=0;if(ql<=mid) ans+=ask_sum(k<<1,ql,qr);if(qr>mid) ans+=ask_sum(k<<1|1,ql,qr);return ans; }IL int q_max(int u,int v){int ans=-0x7fffffff;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);ans=max(ans,ask_max(1,id[top[u]],id[u]));u=f[top[u]];}if(dep[u]<dep[v]) swap(u,v);ans=max(ans,ask_max(1,id[v],id[u]));return ans; }IL int q_sum(int u,int v){int ans=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);ans+=ask_sum(1,id[top[u]],id[u]);u=f[top[u]];}if(dep[u]<dep[v]) swap(u,v);ans+=ask_sum(1,id[v],id[u]);return ans; }string s;int main() {scanf("%d",&n);for(int u,v,i=1;i<n;i++){scanf("%d%d",&u,&v);add(u,v),add(v,u);}for(int i=1;i<=n;i++) scanf("%d",&val[i]);dfs1(1,1);dfs2(1,1);build(1,1,n);scanf("%d",&m); for(int u,v,i=1;i<=m;i++){cin>>s;scanf("%d%d",&u,&v);if(s=="CHANGE")change(1,id[u],v);else if(s=="QMAX") printf("%d\n",q_max(u,v));else printf("%d\n",q_sum(u,v));}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/song-/p/9777724.html

總結(jié)

以上是生活随笔為你收集整理的洛谷——P2590 [ZJOI2008]树的统计（树链剖分模板练手）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。