【题目】

【题意】给定n个点的带边权树，m条编号1~m的路径，Q次询问编号区间[L,R]所有链的交集的长度。n<=500000。

【算法】线段树+RMQ-LCA+树链的交

【题解】树链的交：记一条链为(a1,b1)，LCA为c1。另一条链为(a2,b2)，LCA为c2。记a1a2,a1b2,b1a2,b1b2的LCA为d1,d2,d3,d4，按深度排序后得deep[d1]<=deep[d2]<=deep[d3]<=deep[d4]，deep[c1]<=deep[c2]。

两条链有交集当且仅当deep[c1]<=deep[d1]&&deep[c2]<=deep[d3]，此时树链(d3,d4)是两条链的交。（判断是否有交还有另一种方法：一条链的LCA在另一条链上时有交）

基于此，用线段树维护m条链的交集，回答询问。用RMQ-LCA预处理后可以降低复杂度（注意欧拉序开2倍）。

总复杂度O(n log n)。

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=500010;int dfn[maxn*2],p[maxn],first[maxn],deep[maxn],Q[maxn*2][22],c[10],d[10],tot=0,num=0;ll dis[maxn];int logs[maxn*2],n,m;struct edge{
    int v,w,from;}e[maxn*2];struct cyc{
    int x,y;}O[maxn];struct tree{
    int l,r;cyc o;}t[maxn*4];void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int fa){    dfn[++num]=x;    if(!p[x])p[x]=num;    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){        deep[e[i].v]=deep[x]+1;        dis[e[i].v]=dis[x]+e[i].w;        dfs(e[i].v,x);        dfn[++num]=x;    }}void prepare(){    logs[0]=-1;for(int i=1;i<=num;i++)logs[i]=logs[i>>1]+1;    for(int i=1;i<=num;i++)Q[i][0]=dfn[i];    for(int j=1;(1<
          
           <=num;j++){        for(int i=1;i+(1<
           
            <=num;i++){ if(deep[Q[i][j-1]]
            
             <<(j-1))][j-1]])Q[i][j]=Q[i][j-1]; else Q[i][j]=Q[i+(1<<(j-1))][j-1]; } }}int lca(int x,int y){ if(p[x]>p[y])swap(x,y); int k=logs[p[y]-p[x]+1]; return deep[Q[p[x]][k]]
             
              <
              
               <
               
                deep[c[2]])swap(c[1],c[2]); if(deep[c[1]]<=deep[d[1]]&&deep[c[2]]<=deep[d[3]])return (cyc){d[3],d[4]};else return (cyc){ 0,0};//} void build(int k,int l,int r){ t[k].l=l;t[k].r=r; if(l==r){t[k].o=O[l];return;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); t[k].o=merge(t[k<<1].o,t[k<<1|1].o);}cyc query(int k,int l,int r){ if(l<=t[k].l&&t[k].r<=r)return t[k].o; int mid=(t[k].l+t[k].r)>>1;cyc x=(cyc){-1,0}; if(l<=mid)x=query(k<<1,l,r); if(r>mid){ if(~x.x)x=merge(x,query(k<<1|1,l,r));else x=query(k<<1|1,l,r);} return x;}int main(){ n=read(); for(int i=1;i
               
              
             
            
           
          
         
        
       
      

 

这题WA之后对拍不出错，发现是生成的数据每个点的父亲编号严格小于它，导致深度关系和编号等价。

然后我在判断c1<=d1&&c2<=d3的时候比较了编号而非深度，于是GG。