题意
给出一棵树,每次询问一个点$x$
到编号在$[l,r]$中的点的距离的最小值。
$n,q\le 10^5$

大概是最简单的动态点分治了,注意开大数组即可,如果改成求最大值这道题会有意思很多

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#define M 100010
#define ls ch[node][0]
#define rs ch[node][1]
using namespace std;
int n,m,num,cnt,root,S;
int head[M],son[M],sz[M],top[M],deep[M],fa[M],f[M],size[M],maxn[M],dis[M],rt[M];
int val[M<<],ch[M<<][];bool vis[M];
struct point{int to,next,dis;}e[M<<];
void add(int from,int to,int dis) {
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
void dfs1(int x) {
sz[x]=;deep[x]=deep[fa[x]]+;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(to==fa[x]) continue;
fa[to]=x,dis[to]=dis[x]+e[i].dis;
dfs1(to),sz[x]+=sz[to];
if(sz[son[x]]<sz[to]) son[x]=to;
}
}
void dfs2(int x,int tp) {
top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa[x]&&e[i].to!=son[x])
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}
int getdis(int x,int y) {
return dis[x]+dis[y]-*dis[lca(x,y)];
}
void getroot(int x,int fa) {
size[x]=;maxn[x]=;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(to==fa||vis[to]) continue;
getroot(to,x),size[x]+=size[to];
maxn[x]=max(maxn[x],size[to]);
}
maxn[x]=max(maxn[x],S-size[x]);
if(maxn[x]<maxn[root]) root=x;
}
void solve(int x,int ff) {
vis[x]=true,f[x]=ff;
for(int i=head[x];i;i=e[i].next) {
int to=e[i].to;
if(vis[to]) continue;
S=size[to],root=,getroot(to,);
solve(root,x);
}
}
void update(int node) {
if(ls) val[node]=min(val[node],val[ls]);
if(rs) val[node]=min(val[node],val[rs]);
}
void insert(int &node,int l,int r,int x,int v) {
if(!node) node=++cnt,val[node]=1e9;
if(l==r) {
val[node]=v;return;
}
int mid=(l+r)/;
if(x<=mid) insert(ls,l,mid,x,v);
else insert(rs,mid+,r,x,v);
update(node);
}
int query(int node,int l,int r,int l1,int r1) {
if(!node) return 1e9;
if(l1<=l&&r1>=r) return val[node];
int mid=(l+r)/,ans=1e9;
if(l1<=mid) ans=min(ans,query(ls,l,mid,l1,r1));
if(r1>mid) ans=min(ans,query(rs,mid+,r,l1,r1));
return ans;
}
void pushin(int x) {
for(int i=x;i;i=f[i])
insert(rt[i],,n,x,getdis(x,i));
}
int ask(int x,int l,int r) {
int ans=1e9;
for(int i=x;i;i=f[i])
ans=min(ans,getdis(x,i)+query(rt[i],,n,l,r));
return ans;
}
int main() {
scanf("%d",&n);
for(int i=;i<n;i++) {
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dfs1(),dfs2(,);
S=maxn[]=n,getroot(,),solve(root,);
for(int i=;i<=n;i++) pushin(i);
scanf("%d",&m);
for(int i=;i<=m;i++) {
int l,r,x;scanf("%d%d%d",&l,&r,&x);
printf("%d\n",ask(x,l,r));
}
return ;
}

最新文章

  1. linux-curl restful接口测试结果格式化
  2. ES6转码器babel的使用
  3. jekyll中文乱码问题
  4. 我的Hibernate入门
  5. Linux - tomcat -jndi数据源配置
  6. 运用经典方法进行横截面数据分类 笔记 (基于R)
  7. 如何创建 Swarm 集群?- 每天5分钟玩转 Docker 容器技术(95)
  8. 给定 n&#215;n 的实数矩阵,每行和每列都是递增的,求这 n^2 个数的中位数。
  9. 【设计模式】简单工厂模式 Simple Factory Pattern
  10. Redis持久化的方式
  11. jquery.filter() 实现元素前3个显示,其余的隐藏
  12. Js将数字转化为中文大写
  13. MATLAB:图像的与、或、非、异或逻辑运算(&amp;、|、~、xor)
  14. windows mongodb最常用命令简单归纳
  15. 微信通过openID发送消息/后台post、get提交并接收数据
  16. Linux Shell中有三种引号的用法
  17. HighCharts使用总结
  18. windows安装tesseract-OCR及使用
  19. 斯坦福大学卷积神经网络教程UFLDL Tutorial - Convolutional Neural Network
  20. JDK的图文安装教程

热门文章

  1. wcur LOCATE +
  2. 每天一個Linux指令- chmod指令
  3. Flask使用日志记录到文件示例
  4. 全面介绍Windows内存管理机制及C++内存分配实例(四):内存映射文件
  5. MySQL初始化设置
  6. 如何在python项目中写出像Django中一样功能的settings
  7. GROUP BY 和 ORDER BY一起使用
  8. Jmeter(八)Jmeter监控tomcat
  9. SCADA 必备函数之 :关于消息的函数
  10. 关联规则之Apriori