HDU 5957 环套树+线段树维护bfs序

题意：

n个点n条边的连通图，边长度都为1，没有重边自环，两种操作：

1.把与x距离小于等于k的所有点的权值增加d  （k<=2）

2.问离x距离小于等于k的所有点的权值和 （k<=2）

思路：

首先这是个环套树，找到环后从环上的每个点开始bfs，处理出每个点向子树走k步的bfs序区间，一层层维护就好了。

分类讨论比较麻烦。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll lazy[4*N],sum[4*N];
int n;
void init()
{
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
}
void up(int x)
{
	sum[x]=sum[x*2]+sum[x*2+1];
}
void down(int x,int l,int r)
{
	if (lazy[x])
	{
		int mid=(l+r)/2;
		sum[x*2]+=(mid-l+1)*lazy[x];
		sum[x*2+1]+=(r-mid)*lazy[x];
		lazy[x*2]+=lazy[x];
		lazy[x*2+1]+=lazy[x];
		lazy[x]=0;
	}
}
void add(int i,int l,int r,int x,int y,int w)
{
	if (x<=l&&r<=y)
	{
		sum[i]+=w*(r-l+1);
		lazy[i]+=w;
		return;
	}
	down(i,l,r);
	int mid=(l+r)/2;
	if (x<=mid) add(i*2,l,mid,x,y,w);
	if (y>mid) add(i*2+1,mid+1,r,x,y,w);
	up(i);
}
ll get(int i,int l,int r,int x,int y)
{
	if (x<=l&&r<=y) return sum[i];
	down(i,l,r);
	int mid=(l+r)/2;
	ll ret=0;
	if (x<=mid) ret+=get(i*2,l,mid,x,y);
	if (y>mid) ret+=get(i*2+1,mid+1,r,x,y);
	return ret;
}

void ad(int l,int r,int w)
{
	if (l>r) return;
	add(1,1,n,l,r,w);
}
ll gt(int l,int r)
{
	if (l>r) return 0;
	return get(1,1,n,l,r);
}

bool vis[N],on[N];
int l[N],r[N];
vector<int>link[N];
int dfs1(int u,int fa)
{
	vis[u]=1;
	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i];
		if (v==fa) continue;
		l[v]=u;
		if (vis[v]) return v;
		int tmp=dfs1(v,u);
		if (tmp) return tmp;
	}
	return 0;
}
int tot;
int q[N],bl[N][3],br[N][3],fa[N];
void bfs(int u)
{
	vis[u]=1;
	q[++tot]=u;
	bl[u][0]=tot; bl[u][1]=bl[u][2]=N;
	br[u][0]=tot; br[u][1]=br[u][2]=0;
	int head=tot;
	while(head<=tot)
	{
		int u=q[head]; head++;
		for (int i=0;i<link[u].size();i++)
		{
			int v=link[u][i];
			if (vis[v]||on[v]) continue;
			q[++tot]=v;
			bl[v][0]=tot; bl[v][1]=bl[v][2]=N;
			br[v][0]=tot; br[v][1]=br[v][2]=0;
			fa[v]=u;
			vis[v]=1;
		}
	}
}

void look(int n)
{
	for (int i=1;i<=n;i++)
	{
		printf("%d %lld\n",i,get(1,1,n,bl[i][0],br[i][0]));
	}
}
char s[10];
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			link[x].push_back(y);
			link[y].push_back(x);
		}

		for (int i=1;i<=n;i++) vis[i]=0,on[i]=0;
		int root=dfs1(1,1);
		r[l[root]]=root; on[root]=1;
        for (int i=l[root];i!=root;i=l[i])  r[l[i]]=i,on[i]=1;

        tot=0;
        for (int i=1;i<=n;i++) vis[i]=0;
        bfs(root);
		for (int i=l[root];i!=root;i=l[i]) bfs(i);
        for (int k=1;k<=2;k++)
			for (int i=tot;i>=1;i--)
			{
				int v=q[i];
				if (on[v]) continue;
				int u=fa[v];
				bl[u][k]=min(bl[u][k],bl[v][k-1]);
				br[u][k]=max(br[u][k],br[v][k-1]);
			}

		init();
        int m; scanf("%d",&m);
		while(m--)
		{
			//look(n);
			scanf("%s",s);
			if (s[0]=='M')
			{
				int u,k,w; scanf("%d%d%d",&u,&k,&w);
				if (k==0) ad(bl[u][0],br[u][0],w);
				if (k==1)
				{
					ad(bl[u][0],br[u][0],w);
					ad(bl[u][1],br[u][1],w);//
					if (on[u])
					{
						int lv=l[u],rv=r[u];
						ad(bl[lv][0],br[lv][0],w);
						ad(bl[rv][0],br[rv][0],w);
					}
					else
					{
						int v=fa[u];
						ad(bl[v][0],br[v][0],w);
					}
				}
				if (k==2)
				{
					ad(bl[u][0],br[u][0],w);
					ad(bl[u][1],br[u][1],w);
					ad(bl[u][2],br[u][2],w);
					if (on[u])
					{
						int lv=l[u];
						ad(bl[lv][0],br[lv][0],w);
						ad(bl[lv][1],br[lv][1],w);
						int rv=r[u];
						ad(bl[rv][0],br[rv][0],w);
						ad(bl[rv][1],br[rv][1],w);
						lv=l[lv];
						if (lv!=rv)
							ad(bl[lv][0],br[lv][0],w);
						else lv=r[lv];
						rv=r[rv];
						if (rv!=lv)
							ad(bl[rv][0],br[rv][0],w);
					}
					else
					{
						int v=fa[u];
						ad(bl[v][0],br[v][0],w);
						ad(bl[v][1],br[v][1],w);
						ad(bl[u][0],br[u][0],-w);
						if (on[v])
						{
							int lv=l[v],rv=r[v];
							ad(bl[lv][0],br[lv][0],w);
							ad(bl[rv][0],br[rv][0],w);
						}
						else
						{
							v=fa[v];
							ad(bl[v][0],br[v][0],w);
						}
					}
				}
			}
			if (s[0]=='Q')
			{
				int u,k,w; scanf("%d%d",&u,&k);
				ll ret=0;
				if (k==0) ret+=gt(bl[u][0],br[u][0]);
				if (k==1)
				{
					ret+=gt(bl[u][0],br[u][0]);
					ret+=gt(bl[u][1],br[u][1]);
					if (on[u])
					{
						int lv=l[u],rv=r[u];
						ret+=gt(bl[lv][0],br[lv][0]);
						ret+=gt(bl[rv][0],br[rv][0]);
					}
					else
					{
						int v=fa[u];
						ret+=gt(bl[v][0],br[v][0]);
					}
				}
				if (k==2)
				{
					ret+=gt(bl[u][0],br[u][0]);
					ret+=gt(bl[u][1],br[u][1]);
					ret+=gt(bl[u][2],br[u][2]);
					if (on[u])
					{
						int lv=l[u];
						ret+=gt(bl[lv][0],br[lv][0]);
						ret+=gt(bl[lv][1],br[lv][1]);
						int rv=r[u];
						ret+=gt(bl[rv][0],br[rv][0]);
						ret+=gt(bl[rv][1],br[rv][1]);
						lv=l[lv];
						if (lv!=rv)
							ret+=gt(bl[lv][0],br[lv][0]);
						else lv=r[lv];
						rv=r[rv];
						if (rv!=lv)
							ret+=gt(bl[rv][0],br[rv][0]);
					}
					else
					{
						int v=fa[u];
						ret+=gt(bl[v][0],br[v][0]);
						ret+=gt(bl[v][1],br[v][1]);
						ret-=gt(bl[u][0],br[u][0]);
						if (on[v])
						{
							int lv=l[v],rv=r[v];
							ret+=gt(bl[lv][0],br[lv][0]);
							ret+=gt(bl[rv][0],br[rv][0]);
						}
						else
						{
							v=fa[v];
							ret+=gt(bl[v][0],br[v][0]);
						}
					}
				}
				printf("%lld\n",ret);
			}

		}

		for (int i=1;i<=n;i++) link[i].clear();
	}
}
/*
1
8
1 2
2 3
3 4
1 4
2 5
3 6
5 7
5 8
12
MODIFY 8 1 5
MODIFY 8 2 2
QUERY 5 0
QUERY 5 1
QUERY 5 2
MODIFY 7 2 2
QUERY 7 2
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2
*/