洛谷P3038 [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 

树链剖分的裸题

但是这个题是在边上进行操作

我们考虑把边上的操作转移到点上

首先想一下最简单的链的情况

对于区间[l,r]的操作会影响r-l+1个点,但只会影响r-l条边

那么我们可以把每条边的边权都放在与它相连的两个点中深度较深的点上

所以我们每次修改的时候都对(l,r]进行修改

查询的时候也如此,

具体怎么实现呢?so easy:joy:

只需要在查询/修改的时候把左区间+1即可

注意特判一下x==y的情况

#include<iostream>
#include<cstdio>
#include<cstring>
#define ls k<<1
#define rs k<<1|1
#define LL long long int 
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}
int root=1;
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
struct Tree
{
    int l,r,f,w,siz;
}T[MAXN];
int a[MAXN],b[MAXN],tot[MAXN],idx[MAXN],deep[MAXN],son[MAXN],top[MAXN],fa[MAXN],cnt=0;
void update(int k)
{
    T[k].w=T[ls].w+T[rs].w;
}
void PushDown(int k)
{
    if(!T[k].f) return ;
    T[ls].w+=T[k].f*T[ls].siz;
    T[rs].w+=T[k].f*T[rs].siz;
    T[ls].f+=T[k].f;
    T[rs].f+=T[k].f;
    T[k].f=0;
}
int dfs1(int now,int f,int dep)
{
    deep[now]=dep;    
    tot[now]=1;
    fa[now]=f;
    int maxson=-1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(edge[i].v==f) continue;
        tot[now]+=dfs1(edge[i].v,now,dep+1);
        if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v;
    }
    return tot[now];
}
void dfs2(int now,int topf)
{
    idx[now]=++cnt;
    a[cnt]=b[now];
    top[now]=topf;
    if(!son[now]) return ;
    dfs2(son[now],topf);
    for(int i=head[now];i!=-1;i=edge[i].nxt)
        if(!idx[edge[i].v])
            dfs2(edge[i].v,edge[i].v);
}
void Build(int k,int ll,int rr)
{
    T[k].l=ll;T[k].r=rr;T[k].siz=rr-ll+1;
    if(ll==rr)
    {
        T[k].w=a[ll];
        return ;
    }
    int mid=(ll+rr)>>1;
    Build(ls,ll,mid);
    Build(rs,mid+1,rr);
    update(k);
}
void IntervalAdd(int k,int ll,int rr,int val)
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].w+=T[k].siz*val;
        T[k].f+=val;
        return ;
    }
    PushDown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(ll<=mid) IntervalAdd(ls,ll,rr,val);
    if(rr>mid)  IntervalAdd(rs,ll,rr,val);
    update(k);
}
int IntervalAsk(int k,int ll,int rr)
{
    int ans=0;
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        ans+=T[k].w;
        return ans;
    }
    PushDown(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(ll<=mid) ans+=IntervalAsk(ls,ll,rr);
    if(rr>mid)  ans+=IntervalAsk(rs,ll,rr);
    return ans;
}
int TreeSum(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])//不在同一条链内 
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ans+=IntervalAsk(1,idx[top[x]],idx[x]);
        x=fa[top[x]]; 
    }
    if(deep[x]>deep[y]) swap(x,y);
    if(x==y) return ans;
    ans+=IntervalAsk(1,idx[x]+1,idx[y]);//需要修改的地方 
    return ans;
}
void TreeAdd(int x,int y)
{
    while(top[x]!=top[y])//不在同一条链内 
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        IntervalAdd(1,idx[top[x]],idx[x],1);
        x=fa[top[x]]; 
    }
    if(deep[x]>deep[y]) swap(x,y);
    if(x==y) return ;
    IntervalAdd(1,idx[x]+1,idx[y],1);//需要修改的地方 
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int N=read(),M=read();
    for(int i=1;i<=N-1;i++)
    {
        int x=read(),y=read();
        AddEdge(x,y);AddEdge(y,x);
    }
    dfs1(root,0,1);
    dfs2(root,root);
    Build(1,1,N);
    while(M--)
    {
        char opt[3];int x,y;
        scanf("%s",opt);x=read();y=read();
        if(opt[0]=='P')
            TreeAdd(x,y);
        else
            printf("%d\n",TreeSum(x,y));
        
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

Flash/Flex学习笔记(53):利用FMS快速创建一个文本聊天室

先来看客户端fla的构成: 第一帧:登录界面 ? 第一帧的代码: import flash.events.MouseEvent; import com.adob...

2109
来自专栏Android点滴积累

ListView:The content of the adapter has changed but ListView did not receive a notification终极解决方法

使用ListView时遇到如下的异常信息: 10-26 18:30:45.085: E/AndroidRuntime(7323): java.lang.Ille...

2307
来自专栏王磊的博客

RabbitMQ交换器Exchange介绍与实践

有了Rabbit的基础知识之后(基础知识详见:深入解读RabbitMQ工作原理及简单使用),本章我们重点学习一下Rabbit里面的exchange(交换器)的知...

871
来自专栏osc同步分享

Gradle 使用实例

总项目结构如下,其中有三个文件: ? gradle.properties 用来配置属性 group=com.yawn version=1.0-SNAPSH...

3228
来自专栏Android 研究

OKHttp源码解析(三)--中阶之线程池和消息队列

android的异步任务一般都是用Thread+Handler或者AsyncTask来实现,其中笔者当初经历过各种各样坑,特别是内存泄漏,当初笔者可是相当的欲死...

2844
来自专栏移动端开发

iOS 从实际出发理解多线程

前言 ----       多线程很多开发者多多少少相信也都有了解,以前有些东西理解的不是很透,慢慢的积累之后,这方面的东西也需要自己好好的总结一下。多线程从我...

2167
来自专栏Spark生态圈

[spark] Standalone模式下Master、WorKer启动流程

而Standalone 作为spark自带cluster manager,需要启动Master和Worker守护进程,本文将从源码角度解析两者的启动流程。Mas...

2852
来自专栏Linux驱动

第1阶段——uboot分析之硬件初始化start.S(4)

分析uboot第一个执行函数_start(cpu/arm920t/start.S)  打开cpu/arm920t/start.S 1 .globl _start...

2698
来自专栏c#开发者

Asp.net Webform 使用Repository模式实现CRUD操作代码生成工具

Asp.net Webform 使用Repository模式实现CRUD操作代码生成工具 介绍 该工具是通过一个github上的开源项目修改的原始作者https...

4448
来自专栏大内老A

[WCF REST] 通过ASP.NET Output Caching实现声明式缓存

ASP.NET的输出缓存(Output Caching)机制允许我们针对整个Web页面或者页面的某个部分(主要针对用户控件)最终呈现的HTML进行缓存。对于后续...

1916

扫码关注云+社区

领取腾讯云代金券