hdu5692 线段树+DFS序

最新推荐文章于 2025-03-09 17:15:52 发布

animalcoder

最新推荐文章于 2025-03-09 17:15:52 发布

阅读量186

点赞数

分类专栏： ACM--线段树文章标签： hdu 线段树 DFS序

本文链接：https://blog.csdn.net/animalcoder/article/details/80013167

版权

ACM--线段树专栏收录该内容

14 篇文章

订阅专栏

本文介绍了一种使用DFS序结合线段树解决特定问题的方法。通过维护DFS序中的时间戳来更新线段树，实现对树形结构中路径的最大值进行高效查询和更新。文章提供了完整的代码实现及调试过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：

中文题

思路：

维护DFS序，得到点i的时间戳le[i]，跟子树最大时间戳re[i]，由于DFS序le[i]跟re[i]必定连续

线段树维护每个点到根节点的路径最大值，叶子节点代表路径的值

修改就是修改le[i]~re[i]的值，查询就是查询最大值

WA点：long long，线段树更新了，但是点值忘记更新了，线段树数组开小，inf开太小

2286ms

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define lc o<<1
#define rc o<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") 
using namespace std;
const int maxn=1e5+5; 
const ll inf=2000000000000000000;
int head[maxn];int nxt[2*maxn];int to[2*maxn];
int le[maxn];int re[maxn]; int rnk[maxn];ll path[maxn];
ll lazy[maxn*4];ll val[maxn*4];ll a[maxn];
int cnt=0,idx=0;
void add(int u,int v){cnt++;nxt[cnt]=head[u];head[u]=cnt;to[cnt]=v;}
void init(){cnt=idx=0;memset(head,-1,sizeof(head));memset(path,0,sizeof(path));}
void dfs(int u,int p)
{
	le[u]=re[u]=++idx;rnk[idx]=u;
	path[u]=path[p]+1ll*a[u];
	for(int i=head[u];i!=-1;i=nxt[i])
	{
		int v=to[i];
		if(v==p)continue;
		dfs(v,u);
		re[u]=max(re[u],re[v]);
	}
}
void pushup(int o){	val[o]=max(val[lc],val[rc]);}
void pushdown(int o)
{
	if(lazy[o]!=0)
	{
		val[lc]+=1ll*lazy[o];
		val[rc]+=1ll*lazy[o];
		lazy[lc]+=lazy[o];
		lazy[rc]+=lazy[o];
		lazy[o]=0;
	}
}
void build(int o,int L,int R)
{
	if(L==R)
	{
		val[o]=path[rnk[L]];
		return ;
	}
	val[o]=-inf;
	lazy[o]=0;
	int m=(L+R)>>1;
	build(lc,L,m);build(rc,m+1,R);
	pushup(o);
}
void update(int o,int L,int R,int ql,int qr,int addval)
{
	if(ql<=L&&qr>=R)
	{
		val[o]+=1ll*addval;
		lazy[o]+=addval;
		return ;
	}
	int m=(L+R)>>1;
	pushdown(o);
	if(ql<=m)update(lc,L,m,ql,qr,addval);
	if(qr>m) update(rc,m+1,R,ql,qr,addval);
	pushup(o);
}
ll query(int o,int L,int R,int ql,int qr)
{
	if(ql<=L&&qr>=R)
		return val[o];
	int m=(L+R)>>1;
	pushdown(o);
	ll ans=-inf;
	if(ql<=m)ans=max(ans,query(lc,L,m,ql,qr));
	if(qr>m) ans=max(ans,query(rc,m+1,R,ql,qr));
	return ans;
}
int main()
{
	int T;int kase=0;
	scanf("%d",&T);
	while(T--)
	{
		int n,q;int u,v;
		scanf("%d %d",&n,&q);init();
		for(int i=1;i<n;i++)
		{
			scanf("%d %d",&u,&v);u++,v++;
			add(u,v);add(v,u);
		}
		for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
		dfs(1,0);build(1,1,n);
		//for(int i=1;i<=n;i++)	printf("i=%d le=%d re=%d path=%d\n ",i,le[i],re[i],path[i]);
		int type=0;ll x,y;
		printf("Case #%d:\n",++kase);
		for(int i=1;i<=q;i++)
		{
			scanf("%d",&type);
			if(type==0)
			{
				scanf("%I64d %I64d",&x,&y);
				x++;
				update(1,1,n,le[x],re[x],y-a[x]);
				a[x]=y;
			}
			if(type==1)
			{
				scanf("%I64d",&x);x++;
				printf("%I64d\n",query(1,1,n,le[x],re[x]));
			}
		}
	}
}