[USACO11DEC] Grass Planting (树链剖分)
题目描述
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!
给出一棵n个节点的树,有m个操作,操作为将一条路径上的边权加一或询问某条边的权值。
输入输出格式
输入格式:
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.
输入输出样例
输入样例#1:
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
输出样例#1:
2
1
2
Solution
树剖板子题,关键是注意统计的是边的权值,不是点的权值。
只需要在每次修改或者查询的时候将其 LCA 的 id +1,即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=100008;
int n,m;
struct sj{
int to;
int next;
}a[maxn*2];
int size,head[maxn];
void add(int x,int y)
{
a[++size].to=y;
a[size].next=head[x];
head[x]=size;
}
int dep[maxn],fa[maxn];
int top[maxn],son[maxn];
int siz[maxn];
void dfs(int x)
{
siz[x]=1;
for(int i=head[x];i;i=a[i].next)
{
int tt=a[i].to;
if(!siz[tt])
{
dep[tt]=dep[x]+1;
fa[tt]=x;
dfs(tt);
siz[x]+=siz[tt];
if(siz[tt]>siz[son[x]])
son[x]=tt;
}
}
}
int id[maxn],num;
void dfs1(int x,int y)
{
top[x]=y;
id[x]=++num;
if(son[x])
dfs1(son[x],y);
for(int i=head[x];i;i=a[i].next)
{
int tt=a[i].to;
if(!top[tt])
if(tt!=son[x])
dfs1(tt,tt);
}
}
int sgm[maxn*4],lazy[maxn*4];
void push_down(int node,int l,int r)
{
int kk=lazy[node],mid=(l+r)/2;
lazy[node*2]+=kk;
lazy[node*2+1]+=kk;
sgm[node*2]+=(mid-l+1)*kk;
sgm[node*2+1]+=(r-mid)*kk;
lazy[node]=0;
}
void change(int node,int left,int right,int l,int r)
{
int v=1;
if(left>r||right<l)
return;
if(left>=l&&right<=r)
{
sgm[node]+=v*(right-left+1);
lazy[node]+=v;
return;
}
push_down(node,left,right);
int dist=(right+left)/2;
change(node*2,left,dist,l,r);
change(node*2+1,dist+1,right,l,r);
sgm[node]=sgm[node*2]+sgm[node*2+1];
return;
}
int query(int node,int left,int right,int l,int r)
{
if(l>right||r<left)
return 0;
if(right<=r&&left>=l)
return sgm[node];
push_down(node,left,right);
int dist=(left+right)/2;
return query(node*2,left,dist,l,r)+query(node*2+1,dist+1,right,l,r);
}
void kuai(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
change(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
change(1,1,n,id[x]+1,id[y]);
return;
}
int check(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans+=query(1,1,n,id[x]+1,id[y]);
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dep[1]=1;
dfs(1);
dfs1(1,1);
while(m--)
{
char ch;
int x,y;
cin>>ch; scanf("%d%d",&x,&y);
if(ch=='Q')
cout<<check(x,y)<<endl;
else
kuai(x,y);
}
}
最新文章
- Python 【第十一章】 Django模版
- mysql online ddl
- 用PHPcms V9四步完成WAP手机站搭建
- IE10,IE11下cookie无法写入问题
- 可访问性级别的C# 修饰符
- js的基础学习
- 回顾javase点滴
- BZOJ 3277: 串/ BZOJ 3473: 字符串 ( 后缀数组 + RMQ + 二分 )
- JS、html打开超链接的几种形式
- GNU中的处理目标文件的若干工具
- iOS----------常用三方库
- PPS--在download DN出现的问题注意:
- Linux内核分析第九次作业
- NX 栈不可执行的绕过方式--ROP链
- iOS编程中比较两个日期的大小
- Swift Optional
- Springboot+ajax传输json数组以及单条数据的方法
- 【elaseticsearch】elaseticsearch启动报错Caused by: org.elasticsearch.transport.BindTransportException: Failed to bind to [9300-9400]
- LeetCode: Word Search 解题报告
- LinkQ 组合查询与分页