洛谷 P2590 BZOJ 1036 [ZJOI2008]树的统计

Time limit 10000 ms//另外，BZOJ只算所有点的总时限，所以可能会放过一些原本会TLE的代码

Memory limit 165888 kB

OS Linux

SourceZJOI2008

吐槽

时隔两年再次写树剖，跟楞半岛，找bug找得想吐，被卡题惨烈程度堪比这次——[HAOI2015]树上操作。

这题被卡的地方在于，单点修改的时候，树上节点的老id没有变成新id，就拿到线段树上做修改了……卡了两天，拿lemon在本地一遍又一遍测试，没有去oj上交，不然有卡评测的嫌疑……

顺便，win10下栈空间好小，4号点、7号点、9号点树比较深，甚至是链，于是win10下跑dfs就给爆栈了，甚至加了#pragma comment(linker,"/STACK:1024000000,1024000000") 也不行（权限不够？）。

这篇博客纯属纪念。

板子题没有解题思路

源代码

#include<cstdio>

#include<algorithm>

int n,q;

struct Edge{

	int nxt,to;

}e[60010];

int head[30010],cnt=1;

void add(int u,int v)

{

	e[cnt]={head[u],v};

	head[u]=cnt++;

	e[cnt]={head[v],u};

	head[v]=cnt++;

}

struct Tree{

	long long w;

	int fa,dep,sz,wson,top,id;

}t[30010];

void dfs1(int u,int fa)

{

	t[u].fa=fa;

	t[u].dep=t[fa].dep+1;

	t[u].sz=1;

	t[u].wson=0;

	int maxn=0;

	for(int i=head[u];i;i=e[i].nxt)

	{

		int v=e[i].to;

		if(v==fa) continue;

		dfs1(v,u);

		int temp=t[v].sz;

		t[u].sz+=temp;

		if(temp>maxn)

		{

			t[u].wson=v;

			maxn=temp;

		}

	}

}

int id=1;

long long a[30010];

void dfs2(int u,int top)

{

	t[u].top=top;

	t[u].id=id;

	a[id]=t[u].w;

	id++;

	if(!t[u].wson) return;

	dfs2(t[u].wson,top);

	for(int i=head[u];i;i=e[i].nxt)

	{

		int v=e[i].to;

		if(v==t[u].fa||v==t[u].wson) continue;

		dfs2(v,v);

	}

}

struct SegTree{

	int l,r;

	long long sum,mx;

}s[120010];

inline void pushup(int x)

{

	s[x].sum=s[x<<1].sum+s[x<<1|1].sum;

	s[x].mx=std::max(s[x<<1].mx,s[x<<1|1].mx);

}

void build(int x,int l,int r)

{

	s[x].l=l;

	s[x].r=r;

	if(l==r)

	{

		s[x].mx=s[x].sum=a[l];

		return;

	}

	int mid=l+r>>1;

	build(x<<1,l,mid);

	build(x<<1|1,mid+1,r);

	pushup(x);

}

void update(int x,int pos,long long k)

{

	if(s[x].l==s[x].r&&s[x].l==pos)

	{

		s[x].mx=s[x].sum=k;

		return;

	}

	int mid=s[x].l+s[x].r>>1;

	if(pos<=mid) update(x<<1,pos,k);

	else update(x<<1|1,pos,k);

	pushup(x);

}

long long quemx(int x,int l,int r)

{

	if(l<=s[x].l&&s[x].r<=r) return s[x].mx;

	int mid=s[x].l+s[x].r>>1;

	long long ans=-1e9;

	if(l<=mid) ans=std::max(ans,quemx(x<<1,l,r));

	if(r>mid) ans=std::max(ans,quemx(x<<1|1,l,r));

	return ans;

}

long long quesum(int x,int l,int r)

{

	if(l<=s[x].l&&s[x].r<=r) return s[x].sum;

	int mid=s[x].l+s[x].r>>1;

	long long ans=0;

	if(l<=mid) ans+=quesum(x<<1,l,r);

	if(r>mid) ans+=quesum(x<<1|1,l,r);

	return ans;

}

inline void change(int pos,long long k)

{

	update(1,t[pos].id,k);//就是这里，我之前写成了update(1,pos,k);

}

long long qmax(int u,int v)

{

	long long ans=-99999999;

	while(t[u].top!=t[v].top)

	{

		if(t[t[u].top].dep<t[t[v].top].dep) std::swap(u,v);

		ans=std::max(ans,quemx(1,t[t[u].top].id,t[u].id));

		u=t[t[u].top].fa;

	}

	if(t[u].id>t[v].id) std::swap(u,v);

	ans=std::max(ans,quemx(1,t[u].id,t[v].id));

	return ans;

}

long long qsum(int u,int v)

{

	long long ans=0;

	while(t[u].top!=t[v].top)

	{

		if(t[t[u].top].dep<t[t[v].top].dep) std::swap(u,v);

		ans+=quesum(1,t[t[u].top].id,t[u].id);

		u=t[t[u].top].fa;

	}

	if(t[u].id>t[v].id) std::swap(u,v);

	ans+=quesum(1,t[u].id,t[v].id);

	return ans;

}

int main()

{

	//freopen("test.in","r",stdin);

	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("%lld",&t[i].w);

	dfs1(1,0);

	dfs2(1,1);

	build(1,1,n);

	scanf("%d",&q);

	while(q--)

	{

		char opt[20]={0};

		int x,y;

		scanf("%s%d%d",opt,&x,&y);

		if(opt[1]=='H') change(x,(long long)y);

		else if(opt[1]=='M') printf("%lld\n",qmax(x,y));

		else printf("%lld\n",qsum(x,y));

	}

}

巴特西

洛谷 P2590 BZOJ 1036 [ZJOI2008]树的统计

吐槽

源代码

最新文章

热门文章