当前位置:网站首页>P2590 [ZJOI2008]树的统计(树剖)

P2590 [ZJOI2008]树的统计(树剖)

2021-08-10 08:43:35 wx6110fa547fd20

P2590 [ZJOI2008]树的统计(树剖)

很裸,区间修改都不需要了,只需用到线段树的单点修改和区间查询。

code

// Problem: P2590 [ZJOI2008]树的统计
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2590
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-04-02 11:41:50
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=3e4+5,M=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
//区间修改 区间求和
#define lx x<<1
#define rx x<<1|1
#define len(x) (a[x].r-a[x].l+1)
struct node{
	int l,r,lz,mx;
	ll s;
}a[N<<2];
inline void re(int x){
	a[x].mx=max(a[lx].mx,a[rx].mx);
	a[x].s=a[lx].s+a[rx].s;
}
inline void pushdown(int x){
	if(a[x].lz){
		a[lx].lz+=a[x].lz,a[rx].lz+=a[x].lz;
		a[lx].s+=len(lx)*a[x].lz;
		a[rx].s+=len(rx)*a[x].lz;
		a[x].lz=0;
	}
}
int val[N],w[N];
void build(int x,int l,int r){
	a[x].l=l,a[x].r=r;
	if(l==r){
		a[x].s=a[x].mx=w[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lx,l,mid);
	build(rx,mid+1,r);
	re(x);
}
void upd(int x,int l,int r,int val){
	if(a[x].l>=l&&a[x].r<=r){
		a[x].s+=1LL*len(x)*val;
		a[x].lz+=val;return;
	}
	pushdown(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(l<=mid) upd(lx,l,r,val);
	if(r>mid) upd(rx,l,r,val);
	re(x);
}
void upd1(int x,int p,int val){
	if(a[x].l==a[x].r){
		a[x].s=a[x].mx=val;
		return;
	}
	int mid=(a[x].l+a[x].r)>>1;
	if(p<=mid) upd1(lx,p,val);
	else  upd1(rx,p,val);
	re(x);
}
ll que(int x,int l,int r){
	if(a[x].l>=l&&a[x].r<=r) return a[x].s;
	int mid=(a[x].l+a[x].r)>>1;
	pushdown(x);
	ll ans=0;
	if(l<=mid) ans+=que(lx,l,r);
	if(r>mid) ans+=que(rx,l,r);
	return ans;
}
ll quem(int x,int l,int r){
	if(a[x].l>=l&&a[x].r<=r) return a[x].mx;
	int mid=(a[x].l+a[x].r)>>1;
	pushdown(x);
	ll ans=-1e18;
	if(l<=mid) ans=max(ans,quem(lx,l,r));
	if(r>mid) ans=max(ans,quem(rx,l,r));
	return ans;
}
struct edge{
	int to,nt;
}e[N<<1];
int h[N],cnt;
void add(int u,int v){
	e[++cnt]={v,h[u]},h[u]=cnt;
	e[++cnt]={u,h[v]},h[v]=cnt;
}
int sz[N],fa[N],son[N],top[N],dfn[N],dep[N];
void dfs(int u,int f){
	sz[u]=1,fa[u]=f,dep[u]=dep[f]+1;
	for(int i=h[u];i;i=e[i].nt){
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v;
	}
}
int id;
void dfs1(int u,int tp){
	top[u]=tp,dfn[u]=++id;w[id]=val[u];
	if(son[u]) dfs1(son[u],tp);
	for(int i=h[u];i;i=e[i].nt){
		int v=e[i].to;
		if(v!=fa[u]&&v!=son[u]) dfs1(v,v);
	}
}
int upd_c(int x,int y,int z){	//chain update
	 while(top[x]!=top[y]){
	 	if(dep[top[x]]<dep[top[y]]) swap(x,y);
	 	upd(1,dfn[top[x]],dfn[x],z);
	 	x=fa[top[x]];
	 }
	 if(dep[x]<dep[y]) swap(x,y);
	 upd(1,dfn[y],dfn[x],z);
}
ll que_c(int x,int y){		//chain query
	ll ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
	 	ans=(ans+que(1,dfn[top[x]],dfn[x]));
	 	x=fa[top[x]];
	 }
	 if(dep[x]<dep[y]) swap(x,y);
	 ans=(ans+que(1,dfn[y],dfn[x]));
	 return ans;
}
void upd_p(int x,int v){
	upd1(1,dfn[x],v);
}
ll que_mx(int x,int y){
	ll ans=-1e18;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
	 	ans=max(ans,quem(1,dfn[top[x]],dfn[x]));
	 	x=fa[top[x]];
	 }
	 if(dep[x]<dep[y]) swap(x,y);
	 ans=max(ans,quem(1,dfn[y],dfn[x]));
	 return ans;
}
int n;
char str[11];
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&val[i]);
	}
	dfs(1,0),dfs1(1,1);build(1,1,n);
	int q;scanf("%d",&q);
	while(q--){
		int u,v;
		scanf("%s%d%d",str,&u,&v);
		if(str[0]=='Q'&&str[1]=='M'){
			printf("%lld\n",que_mx(u,v));
		}
		else if(str[0]=='Q'&&str[1]=='S'){
			printf("%lld\n",que_c(u,v));
		}
		else {
			upd_p(u,v);
		}
	}
	return 0;
}



      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.
  • 97.
  • 98.
  • 99.
  • 100.
  • 101.
  • 102.
  • 103.
  • 104.
  • 105.
  • 106.
  • 107.
  • 108.
  • 109.
  • 110.
  • 111.
  • 112.
  • 113.
  • 114.
  • 115.
  • 116.
  • 117.
  • 118.
  • 119.
  • 120.
  • 121.
  • 122.
  • 123.
  • 124.
  • 125.
  • 126.
  • 127.
  • 128.
  • 129.
  • 130.
  • 131.
  • 132.
  • 133.
  • 134.
  • 135.
  • 136.
  • 137.
  • 138.
  • 139.
  • 140.
  • 141.
  • 142.
  • 143.
  • 144.
  • 145.
  • 146.
  • 147.
  • 148.
  • 149.
  • 150.
  • 151.
  • 152.
  • 153.
  • 154.
  • 155.
  • 156.
  • 157.
  • 158.
  • 159.
  • 160.
  • 161.
  • 162.
  • 163.
  • 164.
  • 165.
  • 166.
  • 167.
  • 168.
  • 169.
  • 170.
  • 171.
  • 172.
  • 173.
  • 174.
  • 175.
  • 176.
  • 177.
  • 178.
  • 179.
  • 180.
  • 181.
  • 182.
  • 183.
  • 184.
  • 185.
  • 186.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328403

随机推荐