BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)

时间:2022-06-25 06:47:50

首先嘛,还是太弱了,想了好久QAQ

然后,这道题么,明显就是求sigma(size[x]) (x是y的儿子且层树小于k) 然后就可以发现:把前n个节点按深度建可持久化线段树,就能用前缀和维护了

其实不难打= =

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 300010

#define maxm 30000100

struct edges{

int to,next;

}edge[maxn*2];

int next[maxn],l,num;

int addedge(int x,int y){

edge[++l]=(edges){x,next[y]};next[y]=l;

edge[++l]=(edges){y,next[x]};next[x]=l;

return 0;

}

int id[maxn],d[maxn],s[maxn],e[maxn],b[maxn];

int dfs(int x,int y){

id[++num]=x;

d[x]=d[y]+1;

b[x]=num;

for (int i=next[x];i;i=edge[i].next){

if (edge[i].to!=y) {

dfs(edge[i].to,x);

s[x]+=s[edge[i].to]+1;

}

}

e[x]=num;

return 0;

}

struct node{

int lc,rc;long long s;

}t[maxm];

#define lc(x) t[x].lc

#define rc(x) t[x].rc

#define s(x) t[x].s

#define mid ((l+r)>>1)

int build(int x,int l,int r){

if (l!=r) {

lc(x)=build(++num,l,mid);

rc(x)=build(++num,mid+1,r);

}

return x;

}

int ins(int x,int l,int r,int c,int z){

int y=++num;

if (l==r) {s(y)=s(x)+z;return y;}

lc(y)=lc(x);rc(y)=rc(x);

if (mid<c) rc(y)=ins(rc(x),mid+1,r,c,z);

else lc(y)=ins(lc(x),l,mid,c,z);

s(y)=s(lc(y))+s(rc(y));

return y;

}

long long sum(int x,int l,int r,int x1,int y1){

if (l>y1||r<x1) return 0;

if (x1<=l&&r<=y1) return s(x);

if (l==r) return s(x);

return sum(lc(x),l,mid,x1,y1)+sum(rc(x),mid+1,r,x1,y1);

}

int root[maxn];

int main(){

int n,q;

scanf("%d%d",&n,&q);

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

int x,y;

scanf("%d%d",&x,&y);

addedge(x,y);

}

dfs(1,0);

num=0;l=0;

root[0]=++num;

build(1,1,n);

for (int i=1;i<=n;i++)root[i]=ins(root[i-1],1,n,d[id[i]],s[id[i]]);

for (int i=1;i<=q;i++) {

int u,v;

scanf("%d%d",&u,&v);

printf("%lld\n",s[u]*1ll*min(v,d[u]-1)+sum(root[e[u]],1,n,d[u]+1,d[u]+v)-sum(root[b[u]],1,n,d[u]+1,d[u]+v));

}

return 0;

}

BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)的更多相关文章

  1. 【BZOJ-3653】谈笑风生 DFS序 &plus; 可持久化线段树

    3653: 谈笑风生 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 628  Solved: 245[Submit][Status][Discuss] ...

  2. 【bzoj4771】七彩树 树链的并&plus;STL-set&plus;DFS序&plus;可持久化线段树

    题目描述 给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点.每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i].如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色.定义 ...

  3. &lbrack;BZOJ 3123&rsqb; &lbrack;SDOI 2013&rsqb;森林&lpar;可持久化线段树&plus;并查集&plus;启发式合并&rpar;

    [BZOJ 3123] [SDOI 2013]森林(可持久化线段树+启发式合并) 题面 给出一个n个节点m条边的森林,每个节点都有一个权值.有两种操作: Q x y k查询点x到点y路径上所有的权值中 ...

  4. Codeforces Round &num;442 &lpar;Div&period; 2&rpar; E Danil and a Part-time Job &lpar;dfs序加上一个线段树区间修改查询&rpar;

    题意: 给出一个具有N个点的树,现在给出两种操作: 1.get x,表示询问以x作为根的子树中,1的个数. 2.pow x,表示将以x作为根的子树全部翻转(0变1,1变0). 思路:dfs序加上一个线 ...

  5. BZOJ&period;2653&period;&lbrack;国家集训队&rsqb;middle&lpar;可持久化线段树 二分&rpar;

    BZOJ 洛谷 求中位数除了\(sort\)还有什么方法?二分一个数\(x\),把\(<x\)的数全设成\(-1\),\(\geq x\)的数设成\(1\),判断序列和是否非负. 对于询问\(( ...

  6. hdu5692【dfs序】【线段树】

    Snacks Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Sub ...

  7. bzoj 4504&colon; K个串 可持久化线段树&plus;堆

    题目: Description 兔子们在玩k个串的游戏.首先,它们拿出了一个长度为n的数字序列,选出其中的一 个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次). 兔子们想 ...

  8. bzoj 3514&colon; GERALD07加强版 lct&plus;可持久化线段树

    题目大意: N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数. 题解: 这道题考试的时候没想出来 于是便爆炸了 结果今天下午拿出昨天准备的题表准备做题的时候 题表里就有这题 ...

  9. 【62测试】【状压dp】【dfs序】【线段树】

    第一题: 给出一个长度不超过100只包含'B'和'R'的字符串,将其无限重复下去. 比如,BBRB则会形成 BBRBBBRBBBRB 现在给出一个区间[l,r]询问该区间内有多少个字符'B'(区间下标 ...

随机推荐

  1. &lbrack;常见问题&rsqb;Project facet Java versin 1&period;8 is not support&period;

    发生这个问题的原因是我们的java编译环境(JDK版本),与tomcat运行环境(JDK或JRE版本)不一致导致的. 到eclipse的设置中找到compile项(或右键项目进入),看一下编译环境的J ...

  2. Linux格式化分区报错Could not start &sol;dev&sol;sda No such file or directory 解决办法

    Linux查看已经分好的区[root@linuxidc ~]# fdisk -l /dev/sda   Disk /dev/sda: 21.5 GB, 21474836480 bytes 255 he ...

  3. PostgreSQL的存储系统二:REDOLOG文件存储结构二

    REDOLOG文件里的用户数据和数据文件里的用户数据存储结构相同 几个月前同事给*一家公司培训<pg9 ad admin>时,有个学员提及WAL里记录的内容为Query时的SQL语句(比 ...

  4. 在Release版本下使用VLD

    前提 同Debug版本在VC中配置好VLD的相关信息,拷贝 Visual Leak Detector\bin\Win32目录下所有的文件和vld.ini到工程目标路径下. 强制检测 在程序入口处的cp ...

  5. 小a和uim之大逃离

    题目传送门 #include <bits/stdc++.h> using namespace std; #define ll long long #define re register # ...

  6. TRIZ理论的进化法则分析(TRIZ学习笔记)

    人们在创新和完好系统的过程能够遵循一定的规律(或者叫法则).从而降低创新和完好系统过程中的试错成本,以下就TRIZ的八大进化原则来进行说明(这个八大法则是前人们的总结,我这里当然会增加我的理解). 我 ...

  7. JDBC(4)-Result结果集

    1.Result结果集的引入 当我们查询数据库时,返回的是一个二维的结果集,我们这时候需要使用ResultSet来遍历结果集,获取每一行的数据. 2.使用Result遍历查询结果 boolean ne ...

  8. Javascript Array对象 sort&lpar;&rpar;方法,记忆方法,方法扩展

    相信 有很多 同仁们,尤其是初学者,在记住 Array对象 sort() 方法的排序,规则上,有点困难: 其实sort()方法已经在实际工作中用到很多遍了,可当我仔细推敲,这个sort()方法,什么时 ...

  9. Markdown中超链接增加&lowbar;blank的方法

    很遗憾,无法在语法上实现,只能通过额外的的JS代码实现,比如: var links = document.links; for (var i = 0; i < links.length; i++ ...

  10. 手撸IoC

    Ioc的实现 可以把IoC模式看作是工厂模式的升华,可以把IoC看作一个大工厂,只不过这个大工厂里要生成的对象都是XML文件中给出定义的,然后利用Java的反射变成,根据XML中给出的类名生成相应的对 ...