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!
PROBLEM NAME: grassplant
INPUT FORMAT:
* 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.
SAMPLE INPUT (file grassplant.in):
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4
OUTPUT FORMAT:
* Lines 1..???: Each line has the answer to a query, appearing in the
same order as the queries appear in the input.
SAMPLE OUTPUT (file grassplant.out):
2
1
2
這題是樹鏈剖分裸題
因為線段樹-我默認2個子結點的長度一樣，結果白癡了……
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (100000+10)
#define MAXM (200000+10)
typedef long long ll;
ll n,m;
int edge[MAXN],pre[MAXN]={0},next[MAXN]={0},weight[MAXN]={0},size=1;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
struct node
{
int ch[2],s,mark;
node():s(0),mark(0){ch[0]=ch[1]=0;}
}q[MAXN*10];
int root[MAXN]={0},tail=0;
void pushdown(int x,int l,int r)
{
if (l==r||q[x].mark==0) {q[x].mark=0; return;}
if (!q[x].ch[0]) q[x].ch[0]=++tail;
if (!q[x].ch[1]) q[x].ch[1]=++tail;
int m=l+r>>1,c=q[x].mark;
q[x].mark=0;
q[q[x].ch[0]].mark+=c;q[q[x].ch[0]].s+=c*(m-l+1);
q[q[x].ch[1]].mark+=c;q[q[x].ch[1]].s+=c*(r-m-1+1);
}
void ins(int &x,int l,int r,int L,int R,int c)
{
if (!x) x=++tail;//pushdown(x,l,r);
q[x].s+=c*(min(r,R)-max(L,l)+1);
if (L<=l&&r<=R) {q[x].mark+=c;return;}
int m=l+r>>1;
if (L<=m) ins(q[x].ch[0],l,m,L,R,c);
if (m+1<=R) ins(q[x].ch[1],m+1,r,L,R,c);
}
int find(int x,int l,int r,int L,int R)
{
if (!x) return 0;
pushdown(x,l,r);
if (L<=l&&r<=R) return q[x].s;
int ans=0,m=l+r>>1;
if (L<=m) ans+=find(q[x].ch[0],l,m,L,R);
if (m<R) ans+=find(q[x].ch[1],m+1,r,L,R);
return ans;
}
int dep[MAXN]={0},son[MAXN]={0},fa[MAXN]={0},siz[MAXN]={0},w[MAXN]={0},top[MAXN]={0};
void dfs(int x,int f)
{
siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
int tmp=0;
Forp(x)
{
int &v=edge[p];
if (v^f)
{
dfs(v,x);
siz[x]+=siz[v];
if (siz[v]>tmp) son[x]=v,tmp=siz[v];
}
}
}
void dfs2(int x,int f)
{
if (!top[x]) top[x]=x;
if (son[x]) top[son[x]]=top[x];
Forp(x)
{
int &v=edge[p];
if (v^f)
{
dfs2(v,x);
w[v]=p;
}
}
}
void inc(int u,int v)
{
while(top[u]^top[v])
{
int fu=top[u],fv=top[v];
if (dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
if (dep[u]>dep[fu]) ins(root[fu],1,n-1,1,dep[u]-dep[fu],1);
u=fu;
if (w[u]) weight[w[u]]++;u=fa[u];
}
if (dep[u]<dep[v]) swap(u,v);
if (u^v) ins(root[top[u]],1,n-1,dep[v]-dep[top[v]]+1,dep[u]-dep[top[u]],1);
}
int find(int u,int v)
{
int ans=0;
while(top[u]^top[v])
{
int fu=top[u],fv=top[v];
if (dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
if (dep[u]>dep[fu]) ans+=find(root[fu],1,n-1,1,dep[u]-dep[fu]);
u=fu;
if (w[u]) ans+=weight[w[u]];u=fa[u];
}
if (dep[u]<dep[v]) swap(u,v);
if (u^v) ans+=find(root[top[u]],1,n-1,dep[v]-dep[top[v]]+1,dep[u]-dep[top[u]]);
return ans;
}
int main()
{
// freopen("I9.in","r",stdin);
// freopen("grassplant.out","w",stdout);
scanf("%d%d",&n,&m);
For(i,n-1) {int u,v;scanf("%d%d",&u,&v);addedge2(u,v); }
dfs(1,0);dfs2(1,0);
For(i,m)
{
char c[2];
int u,v;
scanf("%s%d%d",c,&u,&v);
switch(c[0])
{
case'P':
{
inc(u,v);
break;
}
default:
{
printf("%d\n",find(u,v));
}
}
}
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (100000+10)
#define MAXM (200000+10)
typedef long long ll;
ll n,m;
int edge[MAXN],pre[MAXN]={0},next[MAXN]={0},weight[MAXN]={0},size=1;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
struct node
{
int ch[2],s,mark;
node():s(0),mark(0){ch[0]=ch[1]=0;}
}q[MAXN*10];
int root[MAXN]={0},tail=0;
void pushdown(int x,int l,int r)
{
if (l==r||q[x].mark==0) {q[x].mark=0; return;}
if (!q[x].ch[0]) q[x].ch[0]=++tail;
if (!q[x].ch[1]) q[x].ch[1]=++tail;
int m=l+r>>1,c=q[x].mark;
q[x].mark=0;
q[q[x].ch[0]].mark+=c;q[q[x].ch[0]].s+=c*(m-l+1);
q[q[x].ch[1]].mark+=c;q[q[x].ch[1]].s+=c*(r-m-1+1);
}
void ins(int &x,int l,int r,int L,int R,int c)
{
if (!x) x=++tail;//pushdown(x,l,r);
q[x].s+=c*(min(r,R)-max(L,l)+1);
if (L<=l&&r<=R) {q[x].mark+=c;return;}
int m=l+r>>1;
if (L<=m) ins(q[x].ch[0],l,m,L,R,c);
if (m+1<=R) ins(q[x].ch[1],m+1,r,L,R,c);
}
int find(int x,int l,int r,int L,int R)
{
if (!x) return 0;
pushdown(x,l,r);
if (L<=l&&r<=R) return q[x].s;
int ans=0,m=l+r>>1;
if (L<=m) ans+=find(q[x].ch[0],l,m,L,R);
if (m<R) ans+=find(q[x].ch[1],m+1,r,L,R);
return ans;
}
int dep[MAXN]={0},son[MAXN]={0},fa[MAXN]={0},siz[MAXN]={0},w[MAXN]={0},top[MAXN]={0};
void dfs(int x,int f)
{
siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
int tmp=0;
Forp(x)
{
int &v=edge[p];
if (v^f)
{
dfs(v,x);
siz[x]+=siz[v];
if (siz[v]>tmp) son[x]=v,tmp=siz[v];
}
}
}
void dfs2(int x,int f)
{
if (!top[x]) top[x]=x;
if (son[x]) top[son[x]]=top[x];
Forp(x)
{
int &v=edge[p];
if (v^f)
{
dfs2(v,x);
w[v]=p;
}
}
}
void inc(int u,int v)
{
while(top[u]^top[v])
{
int fu=top[u],fv=top[v];
if (dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
if (dep[u]>dep[fu]) ins(root[fu],1,n-1,1,dep[u]-dep[fu],1);
u=fu;
if (w[u]) weight[w[u]]++;u=fa[u];
}
if (dep[u]<dep[v]) swap(u,v);
if (u^v) ins(root[top[u]],1,n-1,dep[v]-dep[top[v]]+1,dep[u]-dep[top[u]],1);
}
int find(int u,int v)
{
int ans=0;
while(top[u]^top[v])
{
int fu=top[u],fv=top[v];
if (dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
if (dep[u]>dep[fu]) ans+=find(root[fu],1,n-1,1,dep[u]-dep[fu]);
u=fu;
if (w[u]) ans+=weight[w[u]];u=fa[u];
}
if (dep[u]<dep[v]) swap(u,v);
if (u^v) ans+=find(root[top[u]],1,n-1,dep[v]-dep[top[v]]+1,dep[u]-dep[top[u]]);
return ans;
}
int main()
{
// freopen("I9.in","r",stdin);
// freopen("grassplant.out","w",stdout);
scanf("%d%d",&n,&m);
For(i,n-1) {int u,v;scanf("%d%d",&u,&v);addedge2(u,v); }
dfs(1,0);dfs2(1,0);
For(i,m)
{
char c[2];
int u,v;
scanf("%s%d%d",c,&u,&v);
switch(c[0])
{
case'P':
{
inc(u,v);
break;
}
default:
{
printf("%d\n",find(u,v));
}
}
}
return 0;
}
