[bzoj1036]-[ZJOI2008]树的统计

开始攻略树剖!
(说老实话我也不知道最近该专门攻啥……总之先把省选的知识都过一遍吧)


题目(bzoj)
题目(洛谷)
嗯,树剖模板题。
注意查询的技巧:两个点依次往上跳(类似于倍增向上跳,只不过怎么感觉有时比倍增还快?)
就这样,完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ls id<<1
#define rs id<<1|1
#define inf INT_MAX
#define readf(f) scanf("%lf",&f)
#define N 30005
using namespace std;
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int n,Q;
struct edge{int vk;int nxt;}e[N*2];
struct Segment_tree{int l;int r;int mx;int sum;}t[N<<2];
int tt,head[N];
inline void ad(int u,int v)
{
	e[++tt].vk=v;
	e[tt].nxt=head[u];
	head[u]=tt;
}
int a[N];
char c[15];
int siz[N],f[N],top[N],son[N],rank[N],pre[N],dep[N],idx;
void dfs1(int u,int fa)
{
	siz[u]=1;
	f[u]=fa;
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==fa) continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if (!son[u] || siz[v]>siz[son[u]])
			son[u]=v;
	}
}
void dfs2(int u,int fa)
{
	top[u]=fa;rank[u]=++idx;
	pre[rank[u]]=u;
	if (!son[u]) return;
	dfs2(son[u],fa);
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==son[u] || v==f[u]) continue;
		dfs2(v,v);
	}
}
inline void up(int id)
{
	t[id].mx=max(t[ls].mx,t[rs].mx);
	t[id].sum=t[ls].sum+t[rs].sum;
}
void build(int l,int r,int id)
{
	t[id].l=l,t[id].r=r;
	if (l==r)
	{
		t[id].mx=t[id].sum=a[pre[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls),build(mid+1,r,rs);
	up(id);
}
void update(int pos,int val,int id)
{
	int l=t[id].l,r=t[id].r;
	if (l==pos && r==pos)
	{
		t[id].sum=val;
		t[id].mx=val;
		return;
	}
	int mid=(l+r)>>1;
	if (pos<=mid) update(pos,val,ls);
	else update(pos,val,rs);
	up(id);
}
int qsum(int l,int r,int id)
{
	int L=t[id].l,R=t[id].r;
	if (L==l && R==r){return t[id].sum;}
	int mid=(L+R)>>1;
	if (r<=mid) return qsum(l,r,ls);
	else if (l>mid) return qsum(l,r,rs);
	else return qsum(l,mid,ls)+qsum(mid+1,r,rs);
}
int qmax(int l,int r,int id)
{
	int L=t[id].l,R=t[id].r;
	if (L==l && R==r){return t[id].mx;}
	int mid=(L+R)>>1;
	if (r<=mid) return qmax(l,r,ls);
	else if (l>mid) return qmax(l,r,rs);
	else return max(qmax(l,mid,ls),qmax(mid+1,r,rs));
}
inline int QMAX(int x,int y)
{
	int f1=top[x],f2=top[y],ret=-inf;
	while (f1!=f2)
	{
		if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
		ret=max(ret,qmax(rank[f1],rank[x],1));
		x=f[f1];f1=top[x];
	}
	if (dep[x]>dep[y]) swap(x,y);
	ret=max(ret,qmax(rank[x],rank[y],1));
	return ret;
}
inline int QSUM(int x,int y)
{
	int f1=top[x],f2=top[y],ret=0;
	while (f1!=f2)
	{
		if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
		ret+=qsum(rank[f1],rank[x],1);
		x=f[f1];f1=top[x];
	}
	if (dep[x]>dep[y]) swap(x,y);
	ret+=qsum(rank[x],rank[y],1);
	return ret;
}
int main()
{
	read(n);
	for (int i=1;i<n;++i)
	{
		int x,y;
		read(x),read(y);
		ad(x,y),ad(y,x);
	}
	for (int i=1;i<=n;++i) read(a[i]);
	dfs1(1,0);dfs2(1,1);
	build(1,idx,1);
	read(Q);
	while (Q--)
	{
		int x,y;
		cin>>c;
		if (c[1]=='S')
		{
			read(x),read(y);
			printf("%d\n",QSUM(x,y));
		}
		else if (c[1]=='M')
		{
			read(x),read(y);
			printf("%d\n",QMAX(x,y));
		}
		else
		{
			read(x),read(y);
			update(rank[x],y,1);
		}
	}
	return 0;
}

另外这份代码在bzoj上会RE,
只需要把那个cin换成scanf就可以了

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注