Problem 3: Grass Planting [Travis Hance, 2011]

Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1  bidirectional roads, such that there is exactly one path between any two pastures.  Bessie, a cow who loves her grazing time, often complains about  how there is no grass on the roads between pastures.  Farmer John loves  Bessie very much, and today he is finally going to plant grass on the
roads.  He will do so using a procedure consisting of M steps (1 <= M <= 100,000).

At each step one of two things will happen:

- FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,

- Bessie will ask about how many patches of grass on a particular road, and  Farmer John must answer her question.

Farmer John is a very poor counter -- help him answer Bessie's questions!

* Line 1: Two space-separated integers N and M

* Lines 2..N: Two space-separated integers describing the endpoints of
a road.

* Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ
is planting grass or simply querying. This is followed by two space-separated integers A_i and B_i (1 <= A_i, B_i <= N)
which describe FJ's action or query.

* Lines 1..???: Each line has the answer to a query, appearing in the
same order as the queries appear in the input.

2
1
2

题目分析：

裸树剖+线段树区间修改区间查询 唯一不同的是这题问的是边权 那么我们把边权换为点权 舍弃最上面的点
修改和查询时注意当x==y 时不进行操作 具体见代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int net[500000],to[500000],head[500000];
int deep[500000],fa[500000],number[500000];
int son[500100],size[500000],top[500000];
int cnt,tot;
struct your
{
	int x,y;
	int sum;
	int add;
}a[500000];
void add(int x,int y)
{
	net[++tot]=head[x];
	to[tot]=y;
	head[x]=tot;
}
void dfs(int x,int temp)
{	
	fa[x]=temp;
	deep[x]=deep[temp]+1;
	size[x]=1;
	for(int i=head[x];i;i=net[i])
		if(to[i]!=temp)
		{
			dfs(to[i],x);
			size[x]+=size[to[i]];
			if(size[son[x]]<size[to[i]]) son[x]=to[i];
		}
}
void dfs2(int x,int temp)
{
	number[x]=++cnt;
	top[x]=temp;
	if(son[x]) dfs2(son[x],temp);
	for(int i=head[x];i;i=net[i])
		if(to[i]!=son[x]&&to[i]!=fa[x]) 
			dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
	a[num].x=dx,a[num].y=dy;
	if(dx==dy) return ;
	int mid=(dx+dy)>>1;
	build(dx,mid,num<<1);
	build(mid+1,dy,num<<1|1);
}
char s[5];
void pushdown(int num)
{
	a[num<<1].sum+=(a[num<<1].y-a[num<<1].x+1)*a[num].add;
	a[num<<1|1].sum+=(a[num<<1|1].y-a[num<<1|1].x+1)*a[num].add;
	a[num<<1].add+=a[num].add;
	a[num<<1|1].add+=a[num].add;
	a[num].add=0;
}
void update(int dx,int dy,int c,int num)
{
	if(a[num].x==dx&&a[num].y==dy) 
	{
		a[num].add+=c;
		a[num].sum+=(a[num].y-a[num].x+1)*c;
		return ;
	}
	if(a[num].add) pushdown(num);
	int mid=(a[num].x+a[num].y)>>1;
	if(dx>mid) update(dx,dy,c,num<<1|1);
	else if(dy<=mid) update(dx,dy,c,num<<1);
	else update(dx,mid,c,num<<1),update(mid+1,dy,c,num<<1|1);
	a[num].sum=a[num<<1|1].sum+a[num<<1].sum;
}
void change(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		update(number[top[x]],number[x],1,1);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	if(x!=y) update(number[x]+1,number[y],1,1);
}
int ask(int dx,int dy,int num)
{
	if(a[num].x==dx&&a[num].y==dy)
		return a[num].sum;
	if(a[num].add) pushdown(num);
	int mid=(a[num].x+a[num].y)>>1;
	if(dx>mid) return ask(dx,dy,num<<1|1);
	if(dy<=mid) return ask(dx,dy,num<<1);
	return ask(dx,mid,num<<1)+ask(mid+1,dy,num<<1|1);
}
int findsum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]]) swap(x,y);
		ans+=ask(number[top[x]],number[x],1);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	if(x!=y) ans+=ask(number[x]+1,number[y],1);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",&s[0]);
		int x,y;
		scanf("%d%d",&x,&y);
		if(s[0]=='P') change(x,y);
		else printf("%d\n",findsum(x,y));
	}
    return 0;
}