Tree chain segmentation (Application of line tree)

[Title Description]

Original title: ZJOI 2008

There are n nodes in a tree with numbers from 1 to N, and each node has a weight w. We will ask you to do something about this tree in the following form:

1.CHANGE u t: change the weight of node u to t;

2.QMAX u v: the maximum weight of nodes on the path from query point u to point v;

3.QSUM u v: the weight sum of nodes on the path from query point u to point v.

Note: nodes on the path from point u to point v include u and V itself.

[input]

The first line is a number n, indicating the number of nodes;

Next n − 1 lines, each line has two integers a and b, indicating that there is an edge between node A and node b;

Next n lines, an integer in each line, the integer wi in line I represents the weight of node i;

The next line, an integer q, represents the total number of operations;

Next, line q, one operation per line, is given in the form of CHANGE u t or QMAX u v or QSUM u v.

[output]

For each QMAX or QSUM operation, an integer is output per line to represent the required result.

[input example]

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

[sample output]

4
1
2
2
10
6
5
6
5
16

[hint]

Data range and tips:

For 100% data, there are 1 ≤ n ≤ 3 × 104, 0 ≤ q ≤ 2 × 105. In the midway operation, the weight w of each node is guaranteed to be between − 30000 and 30000.

#include<bits/stdc++.h>//The procedure explained by xyc
#define lc (k<<1)
#define rc (k<<1|1)
#define mid ((a[k].l+a[k].r)>>1)
using namespace std;
inline void in(int &x){
	int f=1;x=0;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-') f=-f;w=getchar();}
	while(w>='0'&&w<='9'){x=(x<<3)+(x<<1)+(w^48);w=getchar();}
	x*=f;
}
const int N=3e4+10;
struct node{
	int son,fa,deep,size,top,zhi,id;
}p[N];
struct tree{
	int l,r,val,maxn;
}a[N<<2];
int n,m,x,y,tot,cnt;char op[100];
int fir[N],vis[N],rk[N],nxt[N<<1],ver[N<<1];
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;}
void dfs1(int x){
	vis[x]=1,p[x].size=1,p[x].deep=p[p[x].fa].deep+1;int maxn=0;
	for(int i=fir[x];i;i=nxt[i]){
		int y=ver[i];if(vis[y]) continue;
		p[y].fa=x,dfs1(y);p[x].size+=p[y].size;
		if(p[y].size>maxn) maxn=p[y].size,p[x].son=y;
	}
}
void dfs2(int x){
	p[x].id=++cnt,rk[cnt]=x,p[x].top=x==p[p[x].fa].son?p[p[x].fa].top:x;
	if(!p[x].son) return ;dfs2(p[x].son);
	for(int i=fir[x];i;i=nxt[i]) {int y=ver[i];if(!p[y].id) dfs2(y);}
}
void build(int k,int l,int r){
	a[k].l=l,a[k].r=r;
	if(l==r) {a[k].maxn=a[k].val=p[rk[l]].zhi;return;}
	build(lc,l,mid),build(rc,mid+1,r);
	a[k].maxn=max(a[lc].maxn,a[rc].maxn);
	a[k].val=a[lc].val+a[rc].val;
}
void add(int k,int x,int z){
	if(a[k].l==a[k].r){a[k].maxn=a[k].val=z;return;}
	if(x<=mid) add(lc,x,z);else add(rc,x,z);
	a[k].maxn=max(a[lc].maxn,a[rc].maxn);
	a[k].val=a[lc].val+a[rc].val;
}
int asksum(int k,int l,int r){
	if(a[k].l>=l&&a[k].r<=r)return a[k].val;
	int ans=0;
	if(l<=mid) ans+=asksum(lc,l,min(r,mid));
	if(r>mid) ans+=asksum(rc,max(mid+1,l),r);
	return ans;
}
int askmax(int k,int l,int r){
	if(a[k].l>=l&&a[k].r<=r)return a[k].maxn;
	int ans=-N;
	if(l<=mid) ans=max(ans,askmax(lc,l,min(mid,r)));
	if(r>mid) ans=max(ans,askmax(rc,max(mid+1,l),r));
	return ans;
}
int main(){
	in(n);for(int i=1;i<n;i++) in(x),in(y),add(x,y),add(y,x);
	for(int i=1;i<=n;i++) in(p[i].zhi);
	dfs1(1),dfs2(1),build(1,1,n),in(m);
	for(int i=1;i<=m;i++){
		scanf("%s",op),in(x),in(y);
		if(op[3]=='X'){
			int ans=-N;
			while(p[x].top!=p[y].top)
			if(p[p[x].top].deep>p[p[y].top].deep)
			ans=max(ans,askmax(1,p[p[x].top].id,p[x].id)),x=p[p[x].top].fa;
			else ans=max(ans,askmax(1,p[p[y].top].id,p[y].id)),y=p[p[y].top].fa;
			ans=max(ans,askmax(1,min(p[x].id,p[y].id),max(p[x].id,p[y].id)));
			printf("%d\n",ans);
		}
		else if(op[3]=='M'){
			int ans=0;
			while(p[x].top!=p[y].top)
			if(p[p[x].top].deep>p[p[y].top].deep)
			ans+=asksum(1,p[p[x].top].id,p[x].id),x=p[p[x].top].fa;
			else ans+=asksum(1,p[p[y].top].id,p[y].id),y=p[p[y].top].fa;
			ans+=asksum(1,min(p[x].id,p[y].id),max(p[x].id,p[y].id));
			printf("%d\n",ans);
		}
		else add(1,p[x].id,y);
	}
	return 0;
}
#include<cstdio>//Another big guy's annotating program
#include<cstring>
using namespace std;
const int N=31000;
const int M=124000;
int n,q,k=1,first[N],summ,maxmax;
struct Edge{ int v,next;}edge[M];
int num[N];
int father[N],dep[N],size[N],son[N],top[N],seg[N],rev[N];
int maxn[M],sum[M];

int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-48;ch=getchar();}
	return f*s;
}
void addedge(int ui,int vi){
   edge[++k].v=vi;edge[k].next=first[ui];first[ui]=k;
   edge[++k].v=ui;edge[k].next=first[vi];first[vi]=k;	
}
void dfs1(int u,int fa){      //First time dfs 
   size[u]=1;          //u has 1 nodes, including itself 
   father[u]=fa;       //u's father is fa 
   dep[u]=dep[fa]+1;   //The depth of u is the depth of its father fa + 1
   for(int i=first[u];i;i=edge[i].next){   //Exhaustion and all sides at the beginning of u 
   	 int v1=edge[i].v;
   	 if(v1==fa) continue;
   	 dfs1(v1,u);
   	 size[u]+=size[v1];     //The number of nodes contained in u adds up the nodes of the son v1
	 if(size[v1]>size[son[u]])   //If the node number of v1 is more than the node number of son[u] of U 
	     son[u]=v1;      //Renew my son 
   }    	
}
void dfs2(int u,int fa){      //Second times dfs 
	if(son[u]){   //Take the heavy son first to ensure that the position of the heavy path on the line tree is continuous 
		seg[son[u]]=++seg[0];    //The number of son[u] on the line tree is + + seg[0] 
		top[son[u]]=top[u];      //The top node of the heavy path of son[u] is the top node of his father U 
		rev[seg[0]]=son[u];      //The node number of seg[0] on the line tree is son[u]
		dfs2(son[u],u);		 
	}
	for(int i=first[u];i;i=edge[i].next){
		int v1=edge[i].v;
		if(top[v1]) continue;   //If v1 has been accessed, i.e. a son or father, no further access is required
		seg[v1]=++seg[0];  
		rev[seg[0]]=v1;
		top[v1]=v1;    //If (u,v1) is a light edge, v1 is the top node of its heavy path
		dfs2(v1,u); 
	}
}
int max(int x,int y){ if(x>y) return x;return y;}
void build(int k,int l,int r){  //Building line tree
   int mid=(l+r)>>1;
   if(l==r){
   	  maxn[k]=sum[k]=num[rev[l]];
   	  return;
   } 
   build(k<<1,l,mid);
   build((k<<1)+1,mid+1,r);
   sum[k]=sum[k<<1]+sum[(k<<1)+1];
   maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);	
}
void change(int k,int l,int r,int val,int pos){  //Modify pos node to val
   if(pos<l||r<pos) return;   //If not, exit 
   if(l==r&&l==pos){    //If points are found, change 
   	  sum[k]=val;
   	  maxn[k]=val;
   	  return;
   } 
   int mid=(l+r)>>1;
   if(mid>=pos) change(k<<1,l,mid,val,pos);    
   if(mid<pos) change((k<<1)+1,mid+1,r,val,pos);
   sum[k]=sum[k<<1]+sum[(k<<1)+1];
   maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);	   
}
void swap(int &x,int &y){ int temp=x;x=y;y=temp;}
void query(int k,int l,int r,int x,int y){
	if(y<l||x>r) return;
	if(x<=l&&r<=y){
		summ+=sum[k];
		maxmax=max(maxmax,maxn[k]);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) query(k<<1,l,mid,x,y);
	if(mid<y) query((k<<1)+1,mid+1,r,x,y);
}
void ask(int x,int y){  //Path query
   int fx=top[x],fy=top[y];  //Find the top nodes of the paths where xy is located
   while(fx!=fy){       //xy is on the same path when exiting 
   	   if(dep[fx]<dep[fy]){   //Ensure greater depth of x 
   	   	  swap(x,y);swap(fx,fy);  
   	   }
   	   query(1,1,seg[0],seg[fx],seg[x]);
   	   x=father[fx];fx=top[x];
   } 
   if(dep[x]>dep[y]) swap(x,y);    //Ensure that the number of x on the line tree is less than y
   query(1,1,seg[0],seg[x],seg[y]); 
}
int main(){
    n=read();
    for(int i=1;i<n;++i) addedge(read(),read());
    for(int i=1;i<=n;++i) num[i]=read();
    dfs1(1,0);
    seg[0]=1;    //Record the number of the line tree up to now 
	seg[1]=1;    //The positions of root nodes 0 and 1 in the line segment tree are 1 
	top[1]=1;   //The top node of the path where 1 is located is 1 
	rev[1]=1;   //Is the node corresponding to the first position in the line tree 1
	dfs2(1,0); 
	build(1,1,seg[0]);    //Building line tree 
	q=read();
	while(q--){
		char st[10];
		scanf("%s",st);
		int ui=read(),vi=read();
		if(st[0]=='C')
		   change(1,1,seg[0],vi,seg[ui]);
		else{
			summ=0;
			maxmax=-100000000;
			ask(ui,vi);
			if(st[1]=='M') printf("%d\n",maxmax);
			else printf("%d\n",summ);
		}
	}	
	return 0;	
}

Tags: less

Posted on Wed, 06 Nov 2019 09:27:27 -0800 by gooman