洛谷P3038 牧草种植 [树链剖分]

时间：2022-11-09 16:41:45

　　题目传送门

牧草种植

题目描述

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

　　分析：

　　题目翻译还是不够好，容易让人误解。

　　题目大意是，给你一棵树，初始边权值均为0。有两种操作，一种是把x到y之间的最短路径上的每一条边权+1，另一种是询问x到y之间的最短路径边权和。

　　很明显的树剖。但是题目中的操作都是在边上进行的，所以要转换成点操作。因为一个父节点可能有多个子节点，而子节点只有一个父节点，所以可以直接把边权赋给子节点，这样就方便操作了。那后面就是树剖模板了。

　　但是要注意一些小细节，换成点操作后，询问和修改时顶端的点都不要操作，否则就会有冗余边权。

　　Code（比较模板的代码风格，将就着看吧）：

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

int n,m,dfn[N],num[N],id,fa[N];

int head[N],cnt,top[N],size[N];

int dep[N],hson[N],root,dg[N];

int seg[N<<],sign[N<<];

struct Node{int to,next;}edge[N<<];

inline int read()

{

    char ch=getchar();int num=;bool flag=false;

    while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

    while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

    return flag?-num:num;

}

inline void add(int x,int y)

{

    edge[++cnt].to=y;

    edge[cnt].next=head[x];

    head[x]=cnt;

}

inline void dfs1(int u)

{

    size[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(v==fa[u])continue;

        dep[v]=dep[u]+;fa[v]=u;

        dfs1(v);size[u]+=size[v];

        if(size[v]>size[hson[u]])

        hson[u]=v;}

}

inline void dfs2(int u,int now)

{

    dfn[++id]=u;num[u]=id;top[u]=now;

    if(!hson[u])return;dfs2(hson[u],now);

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(v==fa[u]||v==hson[u])continue;

        dfs2(v,v);}

}

inline void pushup(int rt)

{seg[rt]=seg[rt<<]+seg[rt<<|];}

inline void pushdown(int l,int r,int rt)

{

    if(!sign[rt])return;

    int mid=(l+r)>>;

    seg[rt<<]+=sign[rt]*(mid-l+);

    seg[rt<<|]+=sign[rt]*(r-mid);

    sign[rt<<]+=sign[rt];

    sign[rt<<|]+=sign[rt];

    sign[rt]=;

}

inline void build(int l,int r,int rt)

{

    if(l>r)return;

    if(l==r){seg[rt]=;return;}

    int mid=(l+r)>>;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    pushup(rt);

}

inline void update(int l,int r,int rt,int L,int R,int C)

{

    if(l>R||r<L)return;

    if(L<=l&&r<=R){

        seg[rt]+=C*(r-l+);

        sign[rt]+=C;return;}

    int mid=(l+r)>>;

    pushdown(l,r,rt);

    if(L<=mid)update(l,mid,rt<<,L,R,C);

    if(R>mid)update(mid+,r,rt<<|,L,R,C);

    pushup(rt);

}

inline int quary(int l,int r,int rt,int L,int R)

{

    if(l>R||r<L)return ;

    if(L<=l&&r<=R){return seg[rt];}

    int mid=(l+r)>>;int ret=;

    pushdown(l,r,rt);

    if(L<=mid)ret+=quary(l,mid,rt<<,L,R);

    if(R>mid)ret+=quary(mid+,r,rt<<|,L,R);

    return ret;

}

inline void plant(int x,int y)

{

    int fax=top[x],fay=top[y];

    while(fax!=fay){

        if(dep[fax]<dep[fay]){

        swap(fax,fay);swap(x,y);}

        update(,n,,num[fax],num[x],);

        x=fa[fax];fax=top[x];}

    if(x!=y){if(dep[x]>dep[y])swap(x,y);

    update(,n,,num[x]+,num[y],);}

}

inline int get(int x,int y)

{

    int fax=top[x],fay=top[y];int ret=;

    while(fax!=fay){

        if(dep[fax]<dep[fay]){

        swap(fax,fay);swap(x,y);}

        ret+=quary(,n,,num[fax],num[x]);

        x=fa[fax];fax=top[x];}

    if(x!=y){if(dep[x]>dep[y])swap(x,y);

    ret+=quary(,n,,num[x]+,num[y]);}

    return ret;

}

int main()

{

    n=read();m=read();

    int x,y,maxx=-;char op[];

    memset(head,-,sizeof(head));

    for(int i=;i<n;i++){

        x=read();y=read();

        add(x,y);add(y,x);

        dg[x]++;dg[y]++;}

    for(int i=;i<=n;i++)

    if(maxx<dg[i])maxx=dg[i],root=i;

    dep[root]=;fa[root]=;

    dfs1(root),dfs2(root,root);

    build(,n,);

    for(int i=;i<=m;i++){

        scanf("%s",op);

        x=read();y=read();

        if(op[]=='P'){

            plant(x,y);}

        else

            printf("%d\n",get(x,y));}

    return ;

}

相关文章