洛谷 P3038 [USACO11DEC]牧草种植Grass Planting(树链剖分)

时间:2021-08-16 04:18:07

洛谷 P3038 [USACO11DEC]牧草种植Grass Planting(树链剖分)

洛谷 P3038 [USACO11DEC]牧草种植Grass Planting(树链剖分)

题解:仍然是无脑树剖,要注意一下边权,然而这种没有初始边权的题目其实和点权也没什么区别了

代码如下:

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson root<<1
#define rson root<<1|1
using namespace std; struct node
{
int lazy,sum,l,r;
} tr[];
int deep[],fa[],son[],size[],id[],top[],cnt;
vector<int> g[]; void push_up(int root)
{
tr[root].sum=tr[lson].sum+tr[rson].sum;
} void push_down(int root)
{
int mid=(tr[root].l+tr[root].r)>>;
tr[lson].sum+=tr[root].lazy*(mid-tr[root].l+);
tr[lson].lazy+=tr[root].lazy;
tr[rson].sum+=tr[root].lazy*(tr[root].r-mid);
tr[rson].lazy+=tr[root].lazy;
tr[root].lazy=;
} void build(int root,int l,int r)
{
if(l==r)
{
tr[root].l=l;
tr[root].r=r;
tr[root].sum=;
return ;
}
tr[root].l=l;
tr[root].r=r;
int mid=(l+r)>>;
build(lson,l,mid);
build(rson,mid+,r);
push_up(root);
} void update(int root,int l,int r,int val)
{
if(l>r)
{
return;
}
if(l==tr[root].l&&tr[root].r==r)
{
tr[root].sum+=val*(tr[root].r-tr[root].l+);
tr[root].lazy+=val;
return ;
}
if(tr[root].lazy)
{
push_down(root);
}
int mid=(tr[root].l+tr[root].r)>>;
if(l>mid)
{
update(rson,l,r,val);
}
else
{
if(r<=mid)
{
update(lson,l,r,val);
}
else
{
update(lson,l,mid,val);
update(rson,mid+,r,val);
}
}
push_up(root);
} int query(int root,int l,int r)
{
if(l>r)
{
return ;
}
if(l==tr[root].l&&r==tr[root].r)
{
return tr[root].sum;
}
if(tr[root].lazy)
{
push_down(root);
}
int mid=(tr[root].l+tr[root].r)>>;
if(l>mid)
{
return query(rson,l,r);
}
else
{
if(r<=mid)
{
return query(lson,l,r);
}
}
return query(lson,l,mid)+query(rson,mid+,r);
} void dfs1(int now,int f,int dep)
{
deep[now]=dep;
fa[now]=f;
size[now]=;
int maxson=-;
for(int i=; i<g[now].size(); i++)
{
if(g[now][i]==f)
{
continue;
}
dfs1(g[now][i],now,dep+);
size[now]+=size[g[now][i]];
if(size[g[now][i]]>maxson)
{
son[now]=g[now][i];
maxson=size[g[now][i]];
}
}
} void dfs2(int now,int topf)
{
id[now]=++cnt;
top[now]=topf;
if(!son[now])
{
return ;
}
dfs2(son[now],topf);
for(int i=; i<g[now].size(); i++)
{
if(fa[now]==g[now][i]||son[now]==g[now][i])
{
continue;
}
dfs2(g[now][i],g[now][i]);
}
} void path_update(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
{
swap(x,y);
}
update(,id[top[x]],id[x],val);
x=fa[top[x]];
}
if(deep[x]>deep[y])
{
swap(x,y);
}
update(,id[x]+,id[y],val);
} int path_query(int x,int y)
{
int ans=;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])
{
swap(x,y);
}
ans+=query(,id[top[x]],id[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y])
{
swap(x,y);
}
ans+=query(,id[x]+,id[y]);
return ans;
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=; i<=n-; i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs1(,,);
dfs2(,);
build(,,n);
for(int i=; i<=m; i++)
{
int from,to;
char kd;
scanf("\n%c %d %d",&kd,&from,&to);
if(kd=='P')
{
path_update(from,to,);
}
if(kd=='Q')
{
printf("%d\n",path_query(from,to));
}
}
}

洛谷 P3038 [USACO11DEC]牧草种植Grass Planting(树链剖分)的更多相关文章

  1. 洛谷P3038 &lbrack;USACO11DEC&rsqb;牧草种植Grass Planting

    题目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional road ...

  2. 洛谷 P3038 &lbrack;USACO11DEC&rsqb;牧草种植Grass Planting

    题目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional road ...

  3. P3038 &lbrack;USACO11DEC&rsqb;牧草种植Grass Planting

    题目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional road ...

  4. ⌈洛谷1505&RightFloor;⌈BZOJ2157&RightFloor;⌈国家集训队&RightFloor;旅游【树链剖分】

    题目链接 [洛谷] [BZOJ] 题目描述 Ray 乐忠于旅游,这次他来到了T 城.T 城是一个水上城市,一共有 N 个景点,有些景点之间会用一座桥连接.为了方便游客到达每个景点但又为了节约成本,T ...

  5. AC日记——&lbrack;USACO11DEC&rsqb;牧草种植Grass Planting 洛谷 P3038

    题目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional road ...

  6. 树链剖分【p3038】&lbrack;USACO11DEC&rsqb;牧草种植Grass Planting

    表示看不太清. 概括题意 树上维护区间修改与区间和查询. 很明显树剖裸题,切掉,细节处错误T了好久 TAT 代码 #include<cstdio> #include<cstdlib& ...

  7. &lbrack;USACO11DEC&rsqb;牧草种植Grass Planting

    图很丑.明显的树链剖分,需要的操作只有区间修改和区间查询.不过这里是边权,我们怎么把它转成点权呢?对于E(u,v),我们选其深度大的节点,把边权扔给它.因为这是树,所以每个点只有一个父亲,所以每个边权 ...

  8. 【LuoguP3038&sol;&lbrack;USACO11DEC&rsqb;牧草种植Grass Planting】树链剖分&plus;树状数组【树状数组的区间修改与区间查询】

    模拟题,可以用树链剖分+线段树维护. 但是学了一个厉害的..树状数组的区间修改与区间查询.. 分割线里面的是转载的: ----------------------------------------- ...

  9. &lbrack;USACO11DEC&rsqb; Grass Planting &lpar;树链剖分&rpar;

    题目描述 Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional road ...

随机推荐

  1. 查看mysql数据库版本方法总结

    当你接手某个mysql数据库管理时,首先你需要查看维护的mysql数据库版本:当开发人员问你mysql数据库版本时,而恰好你又遗忘了,那么此时也需要去查看mysql数据库的版本............ ...

  2. html标签快速转换思想方法

    function htmlencode(s){ var div = document.createElement('div'); div.appendChild(document.createText ...

  3. express快速搭建web server

    安装express4.x npm install -g express npm install -g express-generator //express命令行工具在4.x分离出来了 express ...

  4. cocoapods遇到error&colon; RPC failed&semi; curl 56 SSLRead&lpar;&rpar; return error -36问题

    在安装cocoapods遇到的问题 [!] /usr/bin/git clone https://github.com/CocoaPods/Specs.git master Cloning into ...

  5. BZOJ 3240 矩阵游戏

    Description 婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的\(n\)行\(m\)列的矩阵(你不用担心她如何存储).她生成的这个矩阵满足一个神奇的性质:若用\(F[i][j]\)来 ...

  6. OpenResty和Resis一些基本的性能配置

    Basics: 1. Ensure that you have not disabled Lua code cache: https://github.com/openresty/lua-nginx- ...

  7. Yii框架基础增删查改

    返回一条数据 Country::find()->one(); 返回所有数据 Country::find()->all(); 返回记录的数量 $country =Country::find( ...

  8. Hive复制分区表和数据

    1. 非分区表: 复制表结构: create table new_table as select * from exists_table where 1=0; 复制表结构和数据: create tab ...

  9. iOS微信实现第三方登录的方法

    这篇文章主要介绍了iOS微信第三方登录实现的全过程,一步一步告诉大家iOS微信实现第三方登录的方法,感兴趣的小伙伴们可以参考一下   一.接入微信第三方登录准备工作.移动应用微信登录是基于OAuth2 ...

  10. 使用rewrite 让php 实现类似asp&period;net 的IHttpModule 进行带参数js文件的参数获取

    asp.net 的IHttpModule 接口具有很大的作用,我们可以使用实现的模块进行全局的控制,但是在学习php 的过程中也想实现类似的功能,查找php 的文档,自己没有找到, 但是我们大家应该知 ...