ORZ blutrex。。。。。。
主席树。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 1000500
#define maxq 1000500
#define maxe 1600500
using namespace std;
struct edge
{
long long v,nxt;
}e[maxe];
struct answer
{
long long sum1,sum2;
};
long long n,q,x,y,nume=,g[maxv],size[maxv],dis[maxv],w[maxv],mx[maxv],mxdis=,cnt=,fw[maxv];
long long root[maxv],ls[maxv<<],rs[maxv<<],val1[maxv<<],val2[maxv<<],tot=;
void addedge(long long u,long long v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs(long long x,long long fath)
{
size[x]=;w[x]=++cnt;mx[x]=w[x];fw[cnt]=x;
for (long long i=g[x];i;i=e[i].nxt)
{
long long v=e[i].v;
if (v!=fath)
{
dis[v]=dis[x]+;mxdis=max(mxdis,dis[v]);
dfs(v,x);
size[x]+=size[v];
mx[x]=max(mx[x],mx[v]);
}
}
}
void build(long long &now,long long left,long long right)
{
now=++tot;val1[now]=val2[now]=;
if (left==right) return;
long long mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
void modify(long long last,long long &now,long long left,long long right,long long pos,long long x)
{
now=++tot;ls[now]=ls[last];rs[now]=rs[last];
val1[now]=val1[last]+x;val2[now]=val2[last]+;
if (left==right) return;
long long mid=(left+right)>>;
if (pos<=mid) modify(ls[last],ls[now],left,mid,pos,x);
else modify(rs[last],rs[now],mid+,right,pos,x);
}
answer merge(answer x,answer y)
{
answer ret;
ret.sum1=x.sum1+y.sum1;
ret.sum2=x.sum2+y.sum2;
return ret;
}
answer ask(long long last,long long now,long long left,long long right,long long l,long long r)
{
answer ret;
if ((left==l) && (right==r))
{
ret.sum1=val1[now]-val1[last];
ret.sum2=val2[now]-val2[last];
return ret;
}
long long mid=(left+right)>>;
if (r<=mid) return ask(ls[last],ls[now],left,mid,l,r);
else if (l>=mid+) return ask(rs[last],rs[now],mid+,right,l,r);
else return merge(ask(ls[last],ls[now],left,mid,l,mid),ask(rs[last],rs[now],mid+,right,mid+,r));
}
int main()
{
scanf("%lld%lld",&n,&q);
for (long long i=;i<=n-;i++)
{
scanf("%lld%lld",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs(,);
build(root[],,mxdis);
for (long long i=;i<=n;i++)
modify(root[i-],root[i],,mxdis,dis[fw[i]],size[fw[i]]);
for (long long i=;i<=q;i++)
{
scanf("%lld%lld",&x,&y);
long long ret=min(dis[x],y)*(size[x]-);
answer regis=ask(root[w[x]-],root[mx[x]],,mxdis,min(dis[x]+,mxdis),min(dis[x]+y,mxdis));
ret+=regis.sum1-regis.sum2;
printf("%lld\n",ret);
}
return ;
}
BZOJ 3653 谈笑风生的更多相关文章
-
BZOJ 3653: 谈笑风生(离线, 长链剖分, 后缀和)
题意 给你一颗有 \(n\) 个点并且以 \(1\) 为根的树.共有 \(q\) 次询问,每次询问两个参数 \(p, k\) .询问有多少对点 \((p, a, b)\) 满足 \(p,a,b\) 为 ...
-
BZOJ.3653.谈笑风生(长链剖分/线段树合并/树状数组)
BZOJ 洛谷 \(Description\) 给定一棵树,每次询问给定\(p,k\),求满足\(p,a\)都是\(b\)的祖先,且\(p,a\)距离不超过\(k\)的三元组\(p,a,b\)个数. ...
-
主席树 || 可持久化线段树 || BZOJ 3653: 谈笑风生 || Luogu P3899 [湖南集训]谈笑风生
题面:P3899 [湖南集训]谈笑风生 题解: 我很喜欢这道题. 因为A是给定的,所以实质是求二元组的个数.我们以A(即给定的P)作为基点寻找答案,那么情况分两类.一种是B为A的父亲,另一种是A为B的 ...
-
【刷题】BZOJ 3653 谈笑风生
Description 设T 为一棵有根树,我们做如下的定义: ? 设a和b为T 中的两个不同节点.如果a是b的祖先,那么称"a比b不知道 高明到哪里去了". ? 设a 和 b 为 ...
-
bzoj 3653 谈笑风生——主席树
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3653 原来一直想怎么线段树合并.可是不会把角标挪一位. 查询的其实是子树内一段深度的点的 s ...
-
bzoj 3653 谈笑风生 —— 主席树
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3653 对于一个 (a,b,c),分成 b 是 a 的祖先和 b 在 a 子树里两部分: 第一 ...
-
BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)
首先嘛,还是太弱了,想了好久QAQ 然后,这道题么,明显就是求sigma(size[x]) (x是y的儿子且层树小于k) 然后就可以发现:把前n个节点按深度建可持久化线段树,就能用前缀和维护了 其实不 ...
-
bzoj 3653: 谈笑风生 可持久化线段树
题目大意 在一棵单位边权的有根树上支持询问: 给定a,k求满足下列条件的有序三元对的个数. a,b,c互不相同 a,b均为c的祖先 a,b树上距离<=k 题解 solution 1 首先我们知道 ...
-
bzoj 3653: 谈笑风生【dfs序+主席树】
考虑b的两种情况,一种是p的祖先,这种点有min(k,de[p]-1)个,然后每个这种b都有si[p]-1个c点可选: 另一种是p的子孙,要求是在p的子树内且deep在de[p]+1~de[p]+k之 ...
随机推荐
-
libiconv的静态编译
./configure --enable-static=yes --prefix=/usr/local/libiconv CentOS安装transmission » Nicky Blog 安装l ...
-
linux mail命令详解
用程序发送邮件有3种方式,分别是: 1.模拟http请求邮件服务商网页实现邮件的发送 2.如果邮件服务商开通了smtp服务,那么可以通过smtp协议通过邮件代理服务商发送邮件 3.自己部署邮件服务器, ...
-
__proto__、prototype和原型对象
一.__proto__ 对象内部存在一个指针,用来指向上一层函数的原型对象.ECMA-262第五版中关这个指针叫[[prototype]],但Firefox.Safari和Chrome在每个对象上都支 ...
-
mysql存储过程的学习(mysql提高执行效率之进阶过程)
1:存储过程: 答:存储过程是sql语句和控制语句的预编译集合,以一个名称存储并作为一个单元处理:存储过程存储在数据库内,可以由应用程序调用执行,而且允许用户声明变量以及进行流程控制,存储类型可以接受 ...
-
Vue项目初始化
1. 生成项目模板 vue init <模板名> 本地文件夹名称2. 进入到生成目录里面 cd xxx npm install3. npm run dev vue项目模板介绍: simpl ...
-
WPF学习笔记(2):准确定位弹出窗
效果图:使弹出的列表框紧随在单元格的下边缘. 第一次,尝试在XAML中设置Popup的定位方式:Placement="Mouse".基本能够定位,但当在输入前移动鼠标,列表框就会随 ...
-
python的内置模块re模块方法详解以及使用
正则表达式 一.普通字符 . 通配符一个.只匹配一个字符 匹配任意除换行符"\n"外的字符(在DOTALL模式中也能匹配换行符 >>> import re ...
-
c# url链接转成二维码图片,再转成byte[]二进制流,输出到前段ajax
需要用到的 dll 添加引用 代码: //获取配置文件设置的url string urllink = ConfigurationManager.AppSettings["urllink&qu ...
-
PHP简单爬虫 爬取免费代理ip 一万条
目标站:http://www.xicidaili.com/ 代码: <?php require 'lib/phpQuery.php'; require 'lib/QueryList.php'; ...
-
ABAP术语-Object Type
Object Type 原文:http://www.cnblogs.com/qiangsheng/archive/2008/03/06/1093159.html Description created ...