首先嘛,还是太弱了,想了好久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序+可持久化线段树)的更多相关文章
-
【BZOJ-3653】谈笑风生 DFS序 + 可持久化线段树
3653: 谈笑风生 Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 628 Solved: 245[Submit][Status][Discuss] ...
-
【bzoj4771】七彩树 树链的并+STL-set+DFS序+可持久化线段树
题目描述 给定一棵n个点的有根树,编号依次为1到n,其中1号点是根节点.每个节点都被染上了某一种颜色,其中第i个节点的颜色为c[i].如果c[i]=c[j],那么我们认为点i和点j拥有相同的颜色.定义 ...
-
[BZOJ 3123] [SDOI 2013]森林(可持久化线段树+并查集+启发式合并)
[BZOJ 3123] [SDOI 2013]森林(可持久化线段树+启发式合并) 题面 给出一个n个节点m条边的森林,每个节点都有一个权值.有两种操作: Q x y k查询点x到点y路径上所有的权值中 ...
-
Codeforces Round #442 (Div. 2) E Danil and a Part-time Job (dfs序加上一个线段树区间修改查询)
题意: 给出一个具有N个点的树,现在给出两种操作: 1.get x,表示询问以x作为根的子树中,1的个数. 2.pow x,表示将以x作为根的子树全部翻转(0变1,1变0). 思路:dfs序加上一个线 ...
-
BZOJ.2653.[国家集训队]middle(可持久化线段树 二分)
BZOJ 洛谷 求中位数除了\(sort\)还有什么方法?二分一个数\(x\),把\(<x\)的数全设成\(-1\),\(\geq x\)的数设成\(1\),判断序列和是否非负. 对于询问\(( ...
-
hdu5692【dfs序】【线段树】
Snacks Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Sub ...
-
bzoj 4504: K个串 可持久化线段树+堆
题目: Description 兔子们在玩k个串的游戏.首先,它们拿出了一个长度为n的数字序列,选出其中的一 个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次). 兔子们想 ...
-
bzoj 3514: GERALD07加强版 lct+可持久化线段树
题目大意: N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数. 题解: 这道题考试的时候没想出来 于是便爆炸了 结果今天下午拿出昨天准备的题表准备做题的时候 题表里就有这题 ...
-
【62测试】【状压dp】【dfs序】【线段树】
第一题: 给出一个长度不超过100只包含'B'和'R'的字符串,将其无限重复下去. 比如,BBRB则会形成 BBRBBBRBBBRB 现在给出一个区间[l,r]询问该区间内有多少个字符'B'(区间下标 ...
随机推荐
-
[常见问题]Project facet Java versin 1.8 is not support.
发生这个问题的原因是我们的java编译环境(JDK版本),与tomcat运行环境(JDK或JRE版本)不一致导致的. 到eclipse的设置中找到compile项(或右键项目进入),看一下编译环境的J ...
-
Linux格式化分区报错Could not start /dev/sda No such file or directory 解决办法
Linux查看已经分好的区[root@linuxidc ~]# fdisk -l /dev/sda Disk /dev/sda: 21.5 GB, 21474836480 bytes 255 he ...
-
PostgreSQL的存储系统二:REDOLOG文件存储结构二
REDOLOG文件里的用户数据和数据文件里的用户数据存储结构相同 几个月前同事给*一家公司培训<pg9 ad admin>时,有个学员提及WAL里记录的内容为Query时的SQL语句(比 ...
-
在Release版本下使用VLD
前提 同Debug版本在VC中配置好VLD的相关信息,拷贝 Visual Leak Detector\bin\Win32目录下所有的文件和vld.ini到工程目标路径下. 强制检测 在程序入口处的cp ...
-
小a和uim之大逃离
题目传送门 #include <bits/stdc++.h> using namespace std; #define ll long long #define re register # ...
-
TRIZ理论的进化法则分析(TRIZ学习笔记)
人们在创新和完好系统的过程能够遵循一定的规律(或者叫法则).从而降低创新和完好系统过程中的试错成本,以下就TRIZ的八大进化原则来进行说明(这个八大法则是前人们的总结,我这里当然会增加我的理解). 我 ...
-
JDBC(4)-Result结果集
1.Result结果集的引入 当我们查询数据库时,返回的是一个二维的结果集,我们这时候需要使用ResultSet来遍历结果集,获取每一行的数据. 2.使用Result遍历查询结果 boolean ne ...
-
Javascript Array对象 sort()方法,记忆方法,方法扩展
相信 有很多 同仁们,尤其是初学者,在记住 Array对象 sort() 方法的排序,规则上,有点困难: 其实sort()方法已经在实际工作中用到很多遍了,可当我仔细推敲,这个sort()方法,什么时 ...
-
Markdown中超链接增加_blank的方法
很遗憾,无法在语法上实现,只能通过额外的的JS代码实现,比如: var links = document.links; for (var i = 0; i < links.length; i++ ...
-
手撸IoC
Ioc的实现 可以把IoC模式看作是工厂模式的升华,可以把IoC看作一个大工厂,只不过这个大工厂里要生成的对象都是XML文件中给出定义的,然后利用Java的反射变成,根据XML中给出的类名生成相应的对 ...