題目描述

一棵樹上有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”的操作，每行輸出一個整數表示要求輸出的結果。

輸入輸出樣例

輸入樣例#1：

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

輸出樣例#1：

4
1
2
2
10
6
5
6
5
16

說明

對于100％的數據，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。

Solution

其實就是個板子,但是好坑啊...
我的query函數如果說不在查詢范圍內的話我就返回0.
然后導致我錯的一塌糊涂...

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxn=100008; const ll inf=19260817000300; struct sj{ll to,next;}a[maxn*2]; ll dep[maxn],fa[maxn]; ll size,n,m,num,pd; ll col[maxn],c[maxn]; ll head[maxn],id[maxn]; ll siz[maxn],zu[maxn],son[maxn]; ll sgm[maxn*4],sgx[maxn*4]; void add(ll x,ll y) {a[++size].to=y;a[size].next=head[x];head[x]=size; }void dfs1(ll x) {siz[x]=1;for(ll i=head[x];i;i=a[i].next){ll tt=a[i].to;if(!siz[tt]){dep[tt]=dep[x]+1;fa[tt]=x;dfs1(tt);siz[x]+=siz[tt];if(siz[tt]>siz[son[x]])son[x]=tt;}} }void dfs2(ll x,ll anc) { zu[x]=anc; c[++num]=col[x]; id[x]=num;if(son[x]) dfs2(son[x],anc);for(ll i=head[x];i;i=a[i].next){ll tt=a[i].to;if(!zu[tt])if(tt==son[x])continue;else dfs2(tt,tt);} }void update(ll node) {sgm[node]=sgm[node*2]+sgm[node*2+1];sgx[node]=max(sgx[node*2],sgx[node*2+1]); }void build(ll node,ll l,ll r) {if(l==r){sgm[node]=c[l];sgx[node]=c[l];return;}ll mid=(l+r)/2;build(node*2,l,mid);build(node*2+1,mid+1,r);update(node); }void change(ll node,ll l,ll r,ll L,ll R,ll cc) {if(l>R||L>r)return;if(l>=L&&r<=R){sgm[node]=cc;sgx[node]=cc;return; }ll mid=(l+r)/2;change(node*2,l,mid,L,R,cc);change(node*2+1,mid+1,r,L,R,cc);update(node); }ll query(ll node,ll l,ll r,ll L,ll R) {if(l>R||L>r)return -inf;if(l>=L&&r<=R){if(pd==1)return sgm[node];else return sgx[node];}ll mid=(l+r)/2;ll llx=query(node*2,l,mid,L,R);ll rrx=query(node*2+1,mid+1,r,L,R);if(pd) {if(llx==-inf)llx=0;if(rrx==-inf)rrx=0;return llx+rrx;}return max(llx,rrx); }ll check(ll x,ll y) {ll rest=0,rest1=-inf;while(zu[x]!=zu[y]){if(dep[zu[x]]<dep[zu[y]])swap(x,y);ll kk=query(1,1,n,id[zu[x]],id[x]);if(pd)rest+=kk;else rest1=max(rest1,kk);x=fa[zu[x]];}if(id[x]>id[y])swap(x,y);ll tt=query(1,1,n,id[x],id[y]);if(pd){rest+=tt;cout<<rest<<endl;return 0;}else rest1=max(tt,rest1);cout<<rest1<<endl; } ll x,y,z; int main() {scanf("%lld",&n);for(ll i=1;i<n;i++){scanf("%lld%lld",&x,&y);add(x,y); add(y,x);}for(ll i=1;i<=n*4;i++)sgx[i]=-inf;for(ll i=1;i<=n;i++)scanf("%lld",&col[i]);dfs1(1);dfs2(1,1);build(1,1,n);scanf("%lld",&m);while(m--){char ch[10];pd=0; scanf("%s",ch);scanf("%lld%lld",&x,&y);if(ch[1]=='M')check(x,y);else if(ch[1]=='S')pd=1,check(x,y);else change(1,1,n,id[x],id[x],y);} }

轉載于:https://www.cnblogs.com/Kv-Stalin/p/9247059.html

總結

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

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