bzoj 1036 洛谷P2590 code[vs] 2460 树的统计

code[vs] 2460
洛谷P2590
bzoj 1036好像bzoj上的数据比较多

<mark>这道题注意可能是负数，因此求最大值的时候要初始化为-inf</mark>

//#include"bits/stdc++.h"
#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
typedef long long LL;
const int maxn=5e5+5;
const LL linf=1e15;
int N,M,Q,R,Time,tot;
LL a[maxn];
LL dep[maxn],sz[maxn],fa[maxn];
LL top[maxn];//用来跳转到这条重链的起始节点
LL sa[maxn];//排第i个的原来是第sa[i]个节点
LL rnk[maxn];//第i个节点排rnk[i]
LL son[maxn];//保存当前节点的重节点
struct Edge
{
	int t,v,nxt;
};
Edge E[maxn<<1];
int head[maxn];
void AddEdge(int aa,int bb,int val)
{
	E[++tot].t=bb;
	E[tot].v=val;
	E[tot].nxt=head[aa];
	head[aa]=tot;
}
void dfs1(int u,int pre,int deep)
{
	dep[u]=deep;
	fa[u]=pre;
	sz[u]=1;
	for(int i=head[u]; i!=-1; i=E[i].nxt)
	{
		int t=E[i].t;
		if(t==pre)continue;
		dfs1(t,u,deep+1);
		sz[u]+=sz[t];
		if(son[u]==-1)son[u]=t;//没有重节点
		else if(sz[t]>sz[son[u]])son[u]=t;//比原来的大
	}
}
void dfs2(int u,int uu)//uu为起始重节点
{
	top[u]=uu;
	rnk[u]=++Time;//Time为时间顺序
	sa[Time]=u;
	if(son[u]==-1)return ;//如果u不在重链上就不继续往下
	dfs2(son[u],uu);
	for(int i=head[u]; i!=-1; i=E[i].nxt)
	{
		int t=E[i].t;
		if(t==fa[u])continue;
		if(t!=son[u])dfs2(t,t);//如果不是重节点，就那么top就会变
	}
}
LL lazy[maxn<<2],sum[maxn<<2],Max[maxn<<2];//线段树的
void pushup(int id)
{
	sum[id]=sum[id<<1]+sum[id<<1|1];
	Max[id]=max(Max[id<<1],Max[id<<1|1]);
}
void Build(int id,int L,int R)
{
	lazy[id]=0;
	if(L==R)
	{
		sum[id]=a[sa[L]];
		Max[id]=sum[id];
		return ;
	}
	int mid=(L+R)>>1;
	Build(id<<1,L,mid);
	Build(id<<1|1,mid+1,R);
	pushup(id);
}
void pushdown(int id,int L,int R)
{
	if(lazy[id]==0)return ;
	int mid=(L+R)>>1;
	lazy[id<<1]+=lazy[id];
	lazy[id<<1|1]+=lazy[id];
	sum[id<<1]+=lazy[id]*(mid-L+1);
	sum[id<<1|1]+=lazy[id]*(R-mid);
	lazy[id]=0;
}
void Add(int id,int L,int R,int qL,int qR,int val)//在线段树[qL,qR]上加权值val 
{
	if(qL<=L&&qR>=R)
	{
		lazy[id]+=val;
		sum[id]+=(LL)val*(R-L+1);
		Max[id]+=val;
		return ;
	}
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	if(qL<=mid)Add(id<<1,L,mid,qL,qR,val);
	if(qR>mid)Add(id<<1|1,mid+1,R,qL,qR,val);
	pushup(id);
}
void AddTree(int u,int v,int val)//在树上加 
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);//重节点深度大的放前面 
		int qL=rnk[top[u]],qR=rnk[u];
		Add(1,1,N,qL,qR,val);//先把重链加上
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);//深度浅的rnk排在前面些
	Add(1,1,N,rnk[u],rnk[v],val);
}
LL query(int id,int L,int R,int qL,int qR)//线段树上询问[qL,qR]的和 
{
	if(qL<=L&&qR>=R)return sum[id];
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	LL res=0;
	if(qL<=mid)res+=query(id<<1,L,mid,qL,qR); 
	if(qR>mid)res+=query(id<<1|1,mid+1,R,qL,qR);
	return res;
}
LL queryMax(int id,int L,int R,int qL,int qR)//线段树上询问[qL,qR]的最大值 
{
	if(qL<=L&&qR>=R)return Max[id];
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	LL mx=-linf;
	if(qL<=mid)mx=max(mx,queryMax(id<<1,L,mid,qL,qR)); 
	if(qR>mid)mx=max(mx,queryMax(id<<1|1,mid+1,R,qL,qR));
	return mx;
}
LL queryTree(int u,int v)//树链上询问u节点到v节点的权值和 
{
	LL res=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);//重节点深度大的放前面 
		int qL=rnk[top[u]],qR=rnk[u];
		res+=query(1,1,N,qL,qR);//先把重链加上
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);//深度浅的rnk排在前面些
	int qL=rnk[u],qR=rnk[v];
	res+=query(1,1,N,qL,qR);
	return res;
}
void Addson(int u,int val)//在u节点以及他的子节点上加权值val 
{
	int qL=rnk[u];
	int qR=rnk[u]+sz[u]-1;
	Add(1,1,N,qL,qR,val);
}
LL queryson(int u)//询问u节点以及子节点的权值和 
{
	int qL=rnk[u];
	int qR=rnk[u]+sz[u]-1;
	return query(1,1,N,qL,qR);
}
LL queryMaxTree(int u,int v)//询问树链上u节点到v节点的最大值 
{
	LL mx=-linf;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);//重节点深度大的放前面 
		int qL=rnk[top[u]],qR=rnk[u];
		mx=max(mx,queryMax(1,1,N,qL,qR));//先把重链加上
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);//深度浅的rnk排在前面些
	int qL=rnk[u],qR=rnk[v];
	mx=max(mx,queryMax(1,1,N,qL,qR));
	return mx;
}
int main()
{
	cin>>N;
	{
		memset(head,-1,sizeof head);
		memset(son,-1,sizeof son);
		tot=Time=0;
		
		for(int i=1; i<N; i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			AddEdge(u,v,1);
			AddEdge(v,u,1);
		}
		for(int i=1; i<=N; i++)scanf("%lld",a+i);
		dfs1(1,-1,0);
		dfs2(1,1);
		Build(1,1,N);
		int t1,t2,v=0;
		char cmd[10];
		cin>>M;
		while(M--)
		{
			scanf("%s",cmd);
			if(cmd[1]=='M')//t1到t2最大值 
			{
				scanf("%d%d",&t1,&t2);
				printf("%lld\n",queryMaxTree(t1,t2));
			}
			else if(cmd[1]=='S')//t1到t2的和 
			{
				scanf("%d%d",&t1,&t2);
				printf("%lld\n",queryTree(t1,t2));
			}
			else if(cmd[1]=='H')//修改点t1 
			{
				scanf("%d%d",&t1,&v);
				LL val=queryTree(t1,t1);
				AddTree(t1,t1,v-val);
			}
		}
	}
}

/* 3 1 2 2 3 -804042 -486095 -54882 10 QMAX 3 2 CHANGE 1 3 QMAX 1 2 CHANGE 3 3 QSUM 1 3 QMAX 1 1 QSUM 3 3 QMAX 2 2 QMAX 1 2 QMAX 3 1 */ 

洛谷 P3178 树上操作

P3178 树上操作
WA的话把权值开成long long 试一试

//#include"bits/stdc++.h"
#include"iostream"
#include"cstring"
#include"cstdio"
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
int N,M,Q,R,Time,tot;
LL a[maxn];
LL dep[maxn],sz[maxn],fa[maxn];
LL top[maxn];//用来跳转到这条重链的起始节点
LL sa[maxn];//排第i个的原来是第sa[i]个节点
LL rnk[maxn];//第i个节点排rnk[i]
LL son[maxn];//保存当前节点的重节点
struct Edge
{
	int t,v,nxt;
};
Edge E[maxn<<1];
int head[maxn];
void AddEdge(int aa,int bb,int val)
{
	E[++tot].t=bb;
	E[tot].v=val;
	E[tot].nxt=head[aa];
	head[aa]=tot;
}
void dfs1(int u,int pre,int deep)
{
	dep[u]=deep;
	fa[u]=pre;
	sz[u]=1;
	for(int i=head[u]; i!=-1; i=E[i].nxt)
	{
		int t=E[i].t;
		if(t==pre)continue;
		dfs1(t,u,deep+1);
		sz[u]+=sz[t];
		if(son[u]==-1)son[u]=t;//没有重节点
		else if(sz[t]>sz[son[u]])son[u]=t;//比原来的大
	}
}
void dfs2(int u,int uu)//uu为起始重节点
{
	top[u]=uu;
	rnk[u]=++Time;//Time为时间顺序
	sa[Time]=u;
	if(son[u]==-1)return ;//如果u不在重链上就不继续往下
	dfs2(son[u],uu);
	for(int i=head[u]; i!=-1; i=E[i].nxt)
	{
		int t=E[i].t;
		if(t==fa[u])continue;
		if(t!=son[u])dfs2(t,t);//如果不是重节点，就那么top就会变
	}
}
LL lazy[maxn<<2],sum[maxn<<2];//线段树的
void pushup(int id)
{
	sum[id]=sum[id<<1]+sum[id<<1|1];
}
void Build(int id,int L,int R)
{
	lazy[id]=0;
	if(L==R)
	{
		
		sum[id]=a[sa[L]];
		return ;
	}
	int mid=(L+R)>>1;
	Build(id<<1,L,mid);
	Build(id<<1|1,mid+1,R);
	pushup(id);
}
void pushdown(int id,int L,int R)
{
	if(lazy[id]==0)return ;
	int mid=(L+R)>>1;
	lazy[id<<1]+=lazy[id];
	lazy[id<<1|1]+=lazy[id];
	sum[id<<1]+=lazy[id]*(mid-L+1);
	sum[id<<1|1]+=lazy[id]*(R-mid);
	lazy[id]=0;
}
void Add(int id,int L,int R,int qL,int qR,LL val)
{
	if(qL<=L&&qR>=R)
	{
		lazy[id]+=val;
		sum[id]+=(LL)val*(R-L+1);
		return ;
	}
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	if(qL<=mid)Add(id<<1,L,mid,qL,qR,val);
	if(qR>mid)Add(id<<1|1,mid+1,R,qL,qR,val);
	pushup(id);
}
void AddTree(int u,int v,LL val)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);//重节点深度大的放前面 
		int qL=rnk[top[u]],qR=rnk[u];
		Add(1,1,N,qL,qR,val);//先把重链加上
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);//深度浅的rnk排在前面些
	Add(1,1,N,rnk[u],rnk[v],val);
}
LL query(int id,int L,int R,int qL,int qR)
{
	if(qL<=L&&qR>=R)return sum[id];
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	LL res=0;
	if(qL<=mid)res+=query(id<<1,L,mid,qL,qR); 
	if(qR>mid)res+=query(id<<1|1,mid+1,R,qL,qR);
	return res;
}
LL queryTree(int u,int v)
{
	LL res=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);//重节点深度大的放前面 
		int qL=rnk[top[u]],qR=rnk[u];
		res+=query(1,1,N,qL,qR);//先把重链加上
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);//深度浅的rnk排在前面些
	int qL=rnk[u],qR=rnk[v];
	res+=query(1,1,N,qL,qR);
	return res;
}
void Addson(int u,LL val)
{
	int qL=rnk[u];
	int qR=rnk[u]+sz[u]-1;
	Add(1,1,N,qL,qR,val);
}
LL queryson(int u)
{
	int qL=rnk[u];
	int qR=rnk[u]+sz[u]-1;
	return query(1,1,N,qL,qR);
}
int main()
{
	cin>>N>>M;
	{
		memset(head,-1,sizeof head);
		memset(son,-1,sizeof son);
		tot=Time=0;
		for(int i=1; i<=N; i++)scanf("%lld",a+i);
		for(int i=1; i<N; i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			AddEdge(u,v,1);
			AddEdge(v,u,1);
		}
		dfs1(1,-1,0);
		dfs2(1,1);
		Build(1,1,N);
		int cmd,t1,t2;
		LL v=0;
		while(M--)
		{
			cin>>cmd;
			if(cmd==1)
			{
				scanf("%d%lld",&t1,&v);
				AddTree(t1,t1,v);
			}
			else if(cmd==2)
			{
				scanf("%d%lld",&t1,&v);
				Addson(t1,v);
			}
			else if(cmd==3)
			{
				scanf("%d",&t1);
				printf("%lld\n",queryTree(1,t1));
			}
		}
	}
}