BZOJ 3653 谈笑风生

时间:2021-10-27 06:47:57

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 谈笑风生的更多相关文章

  1. BZOJ 3653&colon; 谈笑风生(离线&comma; 长链剖分&comma; 后缀和)

    题意 给你一颗有 \(n\) 个点并且以 \(1\) 为根的树.共有 \(q\) 次询问,每次询问两个参数 \(p, k\) .询问有多少对点 \((p, a, b)\) 满足 \(p,a,b\) 为 ...

  2. BZOJ&period;3653&period;谈笑风生&lpar;长链剖分&sol;线段树合并&sol;树状数组&rpar;

    BZOJ 洛谷 \(Description\) 给定一棵树,每次询问给定\(p,k\),求满足\(p,a\)都是\(b\)的祖先,且\(p,a\)距离不超过\(k\)的三元组\(p,a,b\)个数. ...

  3. 主席树 &vert;&vert; 可持久化线段树 &vert;&vert; BZOJ 3653&colon; 谈笑风生 &vert;&vert; Luogu P3899 &lbrack;湖南集训&rsqb;谈笑风生

    题面:P3899 [湖南集训]谈笑风生 题解: 我很喜欢这道题. 因为A是给定的,所以实质是求二元组的个数.我们以A(即给定的P)作为基点寻找答案,那么情况分两类.一种是B为A的父亲,另一种是A为B的 ...

  4. 【刷题】BZOJ 3653 谈笑风生

    Description 设T 为一棵有根树,我们做如下的定义: ? 设a和b为T 中的两个不同节点.如果a是b的祖先,那么称"a比b不知道 高明到哪里去了". ? 设a 和 b 为 ...

  5. bzoj 3653 谈笑风生——主席树

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3653 原来一直想怎么线段树合并.可是不会把角标挪一位. 查询的其实是子树内一段深度的点的 s ...

  6. bzoj 3653 谈笑风生 —— 主席树

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3653 对于一个 (a,b,c),分成 b 是 a 的祖先和 b 在 a 子树里两部分: 第一 ...

  7. BZOJ 3653&colon; 谈笑风生&lpar;DFS序&plus;可持久化线段树&rpar;

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

  8. bzoj 3653&colon; 谈笑风生 可持久化线段树

    题目大意 在一棵单位边权的有根树上支持询问: 给定a,k求满足下列条件的有序三元对的个数. a,b,c互不相同 a,b均为c的祖先 a,b树上距离<=k 题解 solution 1 首先我们知道 ...

  9. bzoj 3653&colon; 谈笑风生【dfs序&plus;主席树】

    考虑b的两种情况,一种是p的祖先,这种点有min(k,de[p]-1)个,然后每个这种b都有si[p]-1个c点可选: 另一种是p的子孙,要求是在p的子树内且deep在de[p]+1~de[p]+k之 ...

随机推荐

  1. libiconv的静态编译

    ./configure --enable-static=yes --prefix=/usr/local/libiconv   CentOS安装transmission » Nicky Blog 安装l ...

  2. linux mail命令详解

    用程序发送邮件有3种方式,分别是: 1.模拟http请求邮件服务商网页实现邮件的发送 2.如果邮件服务商开通了smtp服务,那么可以通过smtp协议通过邮件代理服务商发送邮件 3.自己部署邮件服务器, ...

  3. &lowbar;&lowbar;proto&lowbar;&lowbar;、prototype和原型对象

    一.__proto__ 对象内部存在一个指针,用来指向上一层函数的原型对象.ECMA-262第五版中关这个指针叫[[prototype]],但Firefox.Safari和Chrome在每个对象上都支 ...

  4. mysql存储过程的学习&lpar;mysql提高执行效率之进阶过程&rpar;

    1:存储过程: 答:存储过程是sql语句和控制语句的预编译集合,以一个名称存储并作为一个单元处理:存储过程存储在数据库内,可以由应用程序调用执行,而且允许用户声明变量以及进行流程控制,存储类型可以接受 ...

  5. Vue项目初始化

    1. 生成项目模板 vue init <模板名> 本地文件夹名称2. 进入到生成目录里面 cd xxx npm install3. npm run dev vue项目模板介绍: simpl ...

  6. WPF学习笔记(2):准确定位弹出窗

    效果图:使弹出的列表框紧随在单元格的下边缘. 第一次,尝试在XAML中设置Popup的定位方式:Placement="Mouse".基本能够定位,但当在输入前移动鼠标,列表框就会随 ...

  7. python的内置模块re模块方法详解以及使用

    正则表达式 一.普通字符 .     通配符一个.只匹配一个字符 匹配任意除换行符"\n"外的字符(在DOTALL模式中也能匹配换行符 >>> import re ...

  8. c&num; url链接转成二维码图片,再转成byte&lbrack;&rsqb;二进制流,输出到前段ajax

    需要用到的 dll 添加引用 代码: //获取配置文件设置的url string urllink = ConfigurationManager.AppSettings["urllink&qu ...

  9. PHP简单爬虫 爬取免费代理ip 一万条

    目标站:http://www.xicidaili.com/ 代码: <?php require 'lib/phpQuery.php'; require 'lib/QueryList.php'; ...

  10. ABAP术语-Object Type

    Object Type 原文:http://www.cnblogs.com/qiangsheng/archive/2008/03/06/1093159.html Description created ...