ZJOI2008 树的统计

这是一道比树链剖分板子还板子的题目。

操作:
我们将以下面的形式来要求你对这棵树完成一些操作:

  1. CHANGE u t :把节点 \(u\) 权值改为 \(t\);
  2. QMAX u v :询问点 \(u\) 到点 \(v\) 路径上的节点的最大权值;
  3. QSUM u v :询问点 \(u\) 到点 \(v\) 路径上的节点的权值和。

注意:从点 \(u\) 到点 \(v\) 路径上的节点包括 \(u\)\(v\) 本身。

显然,这是一道树链剖分的题目,对于树的操作考虑线段树。
对于操作一,单点修改,我们不需要懒标记。
对于操作二,维护区间最大值即可。
对于操作三,维护区间和即可。

代码:

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    typedef __uint128_t L;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{
        FastMod(ULL b):b(b),m(ULL((L(1)<<64)/b)){}
        ULL reduce(ULL a){
            ULL q=(ULL)((L(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{
    	char ch;
    	int st[40];
		bool pd;
		inline int read(){
			ch=gc;
			while(ch>'Z'||ch<'A')ch=gc;
			if(ch=='C')return 1;
			ch=gc;
			if(ch=='S')return 2;
			return 3;
		}
		inline void read(int &x){
    		x=0,ch=gc,pd=false;
    		while(!isdigit(ch)){pd=ch=='-'?true:false;ch=gc;}
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
    		if(pd)x=-x;
		}
		inline int write(int a){
			if(a<0)a=-a,pc('-');
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#include<algorithm>
#define P(A) A=-~A
#define NUMBER1 30000
#define tt for(register int i=head[u];~i;i=e[i].next)
#define fione(begin,end) for(register int i=begin;i<=end;P(i))
#define inf 0x7f7f7f7f
#define ls(a) a<<1
#define rs(a) a<<1|1
#define mid (l+r>>1)
#define lson l,mid,ls(rt)
#define rson mid+1,r,rs(rt)
struct Segment{
	inline void push_up(const int &rt){tree[rt]=tree[ls(rt)]+tree[rs(rt)],mx[rt]=std::max(mx[ls(rt)],mx[rs(rt)]);}
	void build(int l,int r,int rt,int *a){
		if(l==r)return tree[rt]=mx[rt]=a[l],void();
		build(lson,a);build(rson,a);
		push_up(rt);
	}
	void one_change(int l,int r,int rt,int p,int date){
		if(l==r)return tree[rt]=mx[rt]=date,void();
		if(p<=mid)one_change(lson,p,date);
		else one_change(rson,p,date);
		push_up(rt);
	}
	int intervalsum(int l,int r,int rt,int x,int y){
		if(x<=l&&r<=y)return tree[rt];
		int res(0);
		if(x<=mid)res+=intervalsum(lson,x,y);
		if(mid<y)res+=intervalsum(rson,x,y);
		push_up(rt);
		return res;
	}
	int intervalmax(int l,int r,int rt,int x,int y){
		if(x<=l&&r<=y)return mx[rt];
		int res(-inf);
		if(x<=mid)res=std::max(res,intervalmax(lson,x,y));
		if(mid<y)res=std::max(res,intervalmax(rson,x,y));
		push_up(rt);
		return res;
	}
	int tree[(NUMBER1<<2)+5],mx[(NUMBER1<<1)+5];
}seg;
struct EDGE{int next,to;}e[(NUMBER1<<2)+5];
int head[NUMBER1+5],tot(0),id[NUMBER1+5],top[NUMBER1+5],son[NUMBER1+5],size[NUMBER1+5],depth[NUMBER1+5],n,cnt(0),a[NUMBER1+5],b[NUMBER1+5],fa[NUMBER1+5];
inline void add(const int &u,const int &v){e[++tot].next=head[u];head[u]=tot,e[tot].to=v;}
void dfs1(int u,int fath,int deep){
	depth[u]=deep,fa[u]=fath,size[u]=1;
	int ms(-1);
	tt{
		if(e[i].to==fath)continue;
		dfs1(e[i].to,u,deep+1);
		size[u]+=size[e[i].to];
		if(size[e[i].to]>ms)ms=size[e[i].to],son[u]=e[i].to;
	}
}
void dfs2(int u,int tf){
	id[u]=++cnt;
	b[cnt]=a[u],top[u]=tf;
	if(!son[u])return;
	dfs2(son[u],tf);
	tt{
		if(e[i].to==fa[u]||e[i].to==son[u])continue;
		dfs2(e[i].to,e[i].to);
	}
}
inline int treesum(int x,int y){
	int ans(0);
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]])std::swap(x,y);
		ans+=seg.intervalsum(1,n,1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(depth[x]>depth[y])std::swap(x,y);
	ans+=seg.intervalsum(1,n,1,id[x],id[y]);
	return ans;
}
inline int treemax(int x,int y){
	int ans(-inf);
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]])std::swap(x,y);
		ans=std::max(ans,seg.intervalmax(1,n,1,id[top[x]],id[x]));
		x=fa[top[x]];
	}
	if(depth[x]>depth[y])std::swap(x,y);
	ans=std::max(ans,seg.intervalmax(1,n,1,id[x],id[y]));
	return ans;
}
signed main(){
	memset(head,-1,sizeof(head));
	int m,x,y,k;
	qrw.read(n);
	fione(1,n-1){
		qrw.read(x);qrw.read(y);
		add(x,y);add(y,x);
	}
	fione(1,n)qrw.read(a[i]);
	dfs1(1,0,1);
	dfs2(1,1);
	seg.build(1,n,1,b);
	qrw.read(m);
	while(m--){
		k=qrw.read();
		qrw.read(x);
		qrw.read(y); 
		switch(k){
			case 1:seg.one_change(1,n,1,id[x],y);break;
			case 2:qrw.write(treesum(x,y));break;
			case 3:qrw.write(treemax(x,y));break;
		}
	}
	fsh;
    exit(0);
    return 0;
}

热门相关:超武穿梭   夫人你马甲又掉了   战神   夫人你马甲又掉了   横行霸道