hdu6110：路径交

$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 ;
 }