当前位置：编程学习 > C/C++ >>

usaco 2011 Dec Gold(Grass Planting-树链剖分第一题)

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
补充：软件开发 , C++ ,

上一个：深究递归和迭代的区别、联系、优缺点及实例对比
下一个：poj 1065 Wooden Sticks

更多图片编程知识:
更多C/C++疑问解答：
关于c++的cout输出的问题。
在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
全国计算机二级C语言笔试题
已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
c++数据结构内部排序问题，整数排序
2012九月计算机二级C语言全国题库，，急求急求
如果assert只有一个字符串作为参数，是什么意思呢?
C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
为什么用结构体编写的程序输入是，0输不出来啊~~~
将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
为什么这个程序求不出公式？
这个链表倒置的算法请大家分析下
c语言函数库调用
C语言unsigned int纠错
C语言快排求解啊
asp
php
Delphi
Matlab
JSP
Foxpro
JS
C/C++
C#/ASP.NET
VC++
JAVA
VB
汇编语言
html/css
CGI
XML/UML
wap
网站相关
网页素材
python
微信小程序
thinkphp
如果你遇到编程学习难题：
访问www.zzzyk.com 试试
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，