$n \leq 500000$的树给$m \leq 500000$个路径,$q \leq 500000$个询问每次问一个区间的路径交。

路径交口诀:(前方高能)

判有交,此链有彼祖;

取其交,最深两两祖。

说成人话就是:判两条路径有没有交,只要一条链的lca在另一条链上就一定有交;取两条路径的交,把两条路径的端点两两求出四对lca,最深那两个就是路径交。

证明?我会还用口诀!

由于需要很多很多次查lca,这里用欧拉序+st表求。查区间路径交可以线段树也可以st表,毕竟重复的部分算两次没问题。

 //#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
//#include<time.h>
//#include<complex>
#include<algorithm>
#include<stdlib.h>
using namespace std; int n,m,q;
#define maxn 500011
struct Edge{int to,next,v;}edge[maxn<<]; int first[maxn],le=;
void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}
void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);} int len,dep[maxn],id[maxn],st[maxn<<][],Log[maxn<<];
#define LL long long
LL dis[maxn];
void dfs(int x,int fa)
{
st[++len][]=x; id[x]=len; dep[x]=dep[fa]+;
for (int i=first[x];i;i=edge[i].next)
{
Edge &e=edge[i]; if (e.to==fa) continue;
dis[e.to]=dis[x]+e.v; dfs(e.to,x); st[++len][]=x;
}
} void makest()
{
Log[]=-; for (int i=;i<=len;i++) Log[i]=Log[i>>]+;
for (int j=;j<=;j++)
for (int i=,to=len-(<<j)+;i<=to;i++)
st[i][j]=dep[st[i][j-]]<dep[st[i+(<<(j-))][j-]]?st[i][j-]:st[i+(<<(j-))][j-];
} int lca(int x,int y)
{
if (id[x]>id[y]) {int t=x;x=y;y=t;} x=id[x]; y=id[y];
int l=Log[y-x+];
return dep[st[x][l]]<dep[st[y-(<<l)+][l]]?st[x][l]:st[y-(<<l)+][l];
} struct Line{int x,y;}line[maxn];
bool cmpdep(const int a,const int b) {return dep[a]<dep[b];}
Line combine(Line a,Line b)
{
if (a.x==- || b.x==-) return (Line){-,-};
int l1=lca(a.x,a.y),l2=lca(b.x,b.y);
int t1=lca(l1,b.x),t2=lca(l1,b.y),t3=lca(a.x,l2),t4=lca(a.y,l2);
bool flag=;
if ((t1==l1 && dep[t1]>=dep[l2]) || (t2==l1 && dep[t2]>=dep[l2])) flag=;
if ((t3==l2 && dep[t3]>=dep[l1]) || (t4==l2 && dep[t4]>=dep[l1])) flag=;
if (!flag) return (Line){-,-};
int d[]; d[]=lca(a.x,b.x); d[]=lca(a.x,b.y); d[]=lca(a.y,b.x); d[]=lca(a.y,b.y);
sort(d,d+,cmpdep); return (Line){d[],d[]};
} struct SMT
{
struct Node
{
int ls,rs;
Line com;
}a[maxn<<];
int size,n;
void clear(int m) {size=; n=m;}
void up(int x)
{
int &p=a[x].ls,&q=a[x].rs;
a[x].com=combine(a[p].com,a[q].com);
}
void build(int &x,int L,int R)
{
x=++size;
if (L==R) {a[x].com=line[L]; a[x].ls=a[x].rs=; return;}
int mid=(L+R)>>;
build(a[x].ls,L,mid); build(a[x].rs,mid+,R); up(x);
}
void build() {int x; build(x,,n);}
int ql,qr;
Line Query(int x,int L,int R)
{
if (ql<=L && R<=qr) return a[x].com;
int mid=(L+R)>>; Line ans; bool flag=;
if (ql<=mid) ans=Query(a[x].ls,L,mid),flag=;
if (qr>mid) {if (flag) ans=combine(Query(a[x].rs,mid+,R),ans); else ans=Query(a[x].rs,mid+,R);}
return ans;
}
Line query(int L,int R) {ql=L; qr=R; return Query(,,n);}
}t; int main()
{
scanf("%d",&n);
for (int i=,x,y,v;i<n;i++) scanf("%d%d%d",&x,&y,&v),insert(x,y,v);
len=; dfs(,); makest();
scanf("%d",&m);
for (int i=;i<=m;i++) scanf("%d%d",&line[i].x,&line[i].y);
t.clear(m); t.build();
scanf("%d",&q);
while (q--)
{
int x,y; scanf("%d%d",&x,&y);
Line ans=t.query(x,y);
printf("%lld\n",dis[ans.x]+dis[ans.y]-*dis[lca(ans.x,ans.y)]);
}
return ;
}

最新文章

  1. 提升mysql性能的建议
  2. MySql开始日期、结束日期查询
  3. ubuntu14.04 server 安装vmware worktation 12
  4. Base64的编码转换方式
  5. spring boot实战(第十三篇)自动配置原理分析
  6. EF实体框架常见问题
  7. 关于JS异步加载方案
  8. Linux 查看系统硬件信息(实例详解)
  9. MVC3.0+knockout.js+Ajax 实现简单的增删改查
  10. ue4中窗口打开web地址
  11. windows下网络编程UDP
  12. java内存机制和GC垃圾回收机制
  13. 关于在html中直接引入less文件遇到的小问题
  14. 同时安装 Python 2 与Python 3 的方法及pip模块的下载安装
  15. Unity3d项目入门之虚拟摇杆
  16. 47 【golang】mysql操作
  17. PCB特征阻抗计算
  18. 微信企业号-根据code获取成员信息(过期code)
  19. let,const 声明的变量不会绑定给window对象 而var会
  20. [JS] Topic - Object.create vs new

热门文章

  1. AngularJS 表单验证手机号(非必填)
  2. js递归和数组去重(简单便捷的用法)
  3. python+selenium(python基础)
  4. Windows虚拟桌面
  5. Chrome安装助手踩坑
  6. 有n个整数,使其前面各数顺序向后移n-m个位置,最后m个数变成最前面的m个数
  7. 《3+1团队》【Alpha】Scrum meeting 5
  8. 报错:org.springframework.dao.InvalidDataAccessResourceUsageException: could not execute statement; SQL [n/a]; nested exception is org.hibernate.exception.SQLGrammarException: could not execute statement
  9. Java中的代理--proxy
  10. 优化UITableView