题目传送门

先建出来点分树,以每个点为根开线段树,维护点分子树内编号为$[l,r]$的儿子到根的距离最小值

每次查询$x$开始,沿着点分树向上跑,在每个点的线段树的$[l,r]$区间里都查一遍取$min$即可

因为题目让我们求最小值,所以出现重复经过同一条路径的情况并不会让答案变坏

如果让我们求最大值呢?似乎可以用主席树搞搞?(仅仅是口胡有空再想)

 #include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 100005
#define M1 505
#define ll long long
#define uint unsigned int
#define ush unsigned short
using namespace std;
const int inf=0x3f3f3f3f; template <typename _T> void read(_T &ret)
{
ret=; _T fh=; char c=getchar();
while(c<''||c>''){ if(c=='-') fh=-; c=getchar(); }
while(c>=''&&c<=''){ ret=ret*+c-''; c=getchar(); }
ret=ret*fh;
} struct Edge{
int to[N1*],nxt[N1*],val[N1*],head[N1],cte;
void ae(int u,int v,int w)
{ cte++; to[cte]=v; nxt[cte]=head[u]; val[cte]=w; head[u]=cte; }
}e; int lg[N1*],de;
namespace Tree{
int dis[N1],dep[N1],fa[N1],st[N1],ff[N1*][],cur; //ord[N1*2],
void dfs1(int x)
{
int j,v; st[x]=++cur; ff[cur][]=x;
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j]; if(v==fa[x]) continue;
fa[v]=x; dis[v]=dis[x]+e.val[j]; dep[v]=dep[x]+;
dfs1(v); ff[++cur][]=x;
}
}
void init()
{
dep[]=; dfs1();
int i,j;
for(i=,lg[]=;i<=cur;i++) lg[i]=lg[i>>]+;
for(j=;j<=lg[cur];j++)
for(i=;i+(<<j)-<=cur;i++)
ff[i][j]=dep[ff[i][j-]] < dep[ff[i+(<<(j-))][j-]] ? ff[i][j-] : ff[i+(<<(j-))][j-];
}
inline int Dis(int x,int y)
{
int i=st[x],j=st[y],F; if(i>j) swap(i,j);
F=dep[ff[i][lg[j-i+]]] < dep[ff[j-(<<lg[j-i+])+][lg[j-i+]]] ? ff[i][lg[j-i+]] : ff[j-(<<lg[j-i+])+][lg[j-i+]];
return dis[x]+dis[y]-*dis[F];
}
}; struct SEG{
struct node{ int ls,rs,mi; };
node a[N1*]; int root[N1],tot;
inline void pushup(int rt)
{
a[rt].mi=inf;
if(a[rt].ls) a[rt].mi=min(a[rt].mi,a[a[rt].ls].mi);
if(a[rt].rs) a[rt].mi=min(a[rt].mi,a[a[rt].rs].mi);
}
void upd(int x,int l,int r,int &rt,int w)
{
if(!rt) rt=++tot;
if(l==r){ a[rt].mi=w; return; }
int mid=(l+r)>>;
if(x<=mid) upd(x,l,mid,a[rt].ls,w);
else upd(x,mid+,r,a[rt].rs,w);
pushup(rt);
}
int qmi(int L,int R,int l,int r,int rt)
{
if(!rt) return inf;
if(L<=l&&r<=R) return a[rt].mi;
int mid=(l+r)>>; int ans=inf;
if(L<=mid) ans=min(ans,qmi(L,R,l,mid,a[rt].ls));
if(R>mid) ans=min(ans,qmi(L,R,mid+,r,a[rt].rs));
return ans;
}
}s; using Tree::Dis; int n;
int sz[N1],ms[N1],use[N1],pfa[N1],SZ,G; void gra(int x,int dad,int now)
{
int j,v; sz[x]=; ms[x]=;
if(now) s.upd(x,,n,s.root[now],Dis(x,now));
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j]; if(v==dad || use[v]) continue;
gra(v,x,now);
sz[x]+=sz[v]; ms[x]=max(ms[x],sz[v]);
}
ms[x]=max(ms[x],SZ-sz[x]);
if(ms[x]<ms[G]) G=x;
} void main_dfs(int x)
{
int j,v; use[x]=;
s.upd(x,,n,s.root[x],);
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j]; if(use[v]) continue;
SZ=sz[v]; G=; gra(v,x,x); pfa[G]=x;
main_dfs(G);
}
} int main()
{
scanf("%d",&n);
int i,j,x,y,w,Q,q,l,r,D,ans;
for(i=;i<n;i++)
{
read(x), read(y), read(w);
e.ae(x,y,w); e.ae(y,x,w);
}
Tree::init();
ms[]=n; SZ=n; gra(,,); main_dfs(G);
scanf("%d",&Q);
for(q=;q<=Q;q++)
{
read(l), read(r), read(x); ans=inf;
for(y=x;y;y=pfa[y])
{
D=Dis(x,y);
ans=min(ans,D+s.qmi(l,r,,n,s.root[y]));
}
printf("%d\r\n",ans);
}
return ;
}

最新文章

  1. (转)Tomcat数据源连接池加密
  2. ECSHOP去版权与标志
  3. Basic认证
  4. Android Studio 修改 包名 package name
  5. 保护企业的Word文档
  6. 在线的JSON formate工具
  7. loadrunner http协议put模式脚本编写
  8. trash目录: ~/.local/share/Trash
  9. 解析Function.prototype.bind
  10. C++深层复制解决指针悬挂
  11. 52e174ef38c96afbbeabe55d2ec53622 我知道这是什么
  12. Java中泛型数组创建总结
  13. springMVC源码分析--AbstractHandlerMethodMapping注册url和HandlerMethod对应关系(十一)
  14. Android Multimedia框架总结(八)Stagefright框架之AwesomePlayer及数据解析器
  15. Spring注入静态变量的方法,以及CXF如何获取客户端IP
  16. python函数(一)
  17. [LeetCode] 455. Assign Cookies_Easy tag: Sort
  18. mysql8.0版本skip-grant-tables出现的新问题
  19. JSP的学习二(指令与标签)
  20. Linux命令之type - 显示命令的类型

热门文章

  1. Android 应用按返回键异常退出的问题
  2. error: &amp;#39;Can&amp;#39;t connect to local MySQL server through socket &amp;#39;/var/lib/mysql/mysql.sock&amp;#39; (2)&amp;#39;
  3. react 使用
  4. 启动Tomcat任何程序都报错
  5. code+3月赛 loj6299 白金元首与克劳德斯
  6. codevs1036商务旅行(LCA)
  7. canvas 文字转化为粒子
  8. HttpClient Get请求实例
  9. cocos2d-x 不规则碰撞检测 【转载】
  10. 移动web——bootstrap栅格系统