好久没写数据结构了

来补一发

果然写的时候思路极其混乱....

 

---

题意

$ Q$次询问，求树上点的颜色在$ [L,R]$中的所有点到询问点的距离 强制在线

询问次数，树上点数约$ 2·10^5$

---

$ Solution$

首先有

$ dist(x,y)=deep(x)+deep(y)-2·deep(lca(x,y))$

显然这个等式的前两项很容易用前缀和什么的维护

只考虑第三项的话相当于是有边权并且强制在线的

用同样的套路将$ deep(lca(x,y))$转化成对于所有在区间中的点，将其到根的路径区间加

然后查询询问点到根的距离

将所有点按颜色排序 树剖+主席树维护

每次将当前颜色最小的点插入主席树 最多影响$ log^2$个线段

注意需要标记永久化

写的时候思路很不清楚感觉写了假的主席树

---

$my \ code$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define M 150010 #define rt register int#define ll long longusing namespace std;inline ll read(){ ll x=0;char zf=1;char ch=getchar(); while(ch!='-'&&!isdigit(ch))ch=getchar(); if(ch=='-')zf=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int k,m,n,x,y,z,cnt,ans;int dfn[M],top[M],size[M],fa[M],to[M];ll deep[M];vector
             
              
               >e[150010];void dfs(int x,int pre){ size[x]=1;fa[x]=pre; for(auto i:e[x])if(i.first!=pre){ deep[i.first]=deep[x]+i.second; dfs(i.first,x);size[x]+=size[i.first]; }}void dfs2(int x,int chain){ int heavy=0;dfn[x]=++cnt;top[x]=chain;to[cnt]=x; for(auto i:e[x])if(size[i.first]>size[heavy]&&i.first!=fa[x])heavy=i.first; if(!heavy)return; dfs2(heavy,chain); for(auto i:e[x])if(i.first!=heavy&&i.first!=fa[x])dfs2(i.first,i.first);}struct segment{ int ls,rs,tag;ll sum;}a[10000010];int Root[150010];#define up a[x].sum=(ll)a[a[x].ls].sum+a[a[x].rs].sum+(ll)a[x].tag*(deep[to[R]]-deep[fa[to[L]]])void change(int x,int L,int R,int LL,int RR){ const int mid=L+R>>1; if(L>=LL&&R<=RR){ a[x].tag++; up;return; } if(mid>=LL){ if(a[x].ls)a[cnt+1]=a[a[x].ls]; change(a[x].ls=++cnt,L,mid,LL,RR); } if(mid+1<=RR){ if(a[x].rs)a[cnt+1]=a[a[x].rs]; change(a[x].rs=++cnt,mid+1,R,LL,RR); } up;}ll query(int x,int LL,int RR,int L,int R,int cs){ if(!x)x=++cnt;if(LL>R||RR
               
                =L&&RR<=R)return a[x].sum+(ll)cs*(deep[to[RR]]-deep[fa[to[LL]]]); const int mid=LL+RR>>1; return query(a[x].ls,LL,mid,L,R,cs+a[x].tag)+query(a[x].rs,mid+1,RR,L,R,cs+a[x].tag);}void upd(int id,int x){ while(x){ change(Root[id],1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; }}ll query(int id,int x){ if(!id)return 0; ll ans=0; while(x){ ans+=query(Root[id],1,n,dfn[top[x]],dfn[x],0); x=fa[top[x]]; } return ans;}struct peri{ int x,id; bool operator <(const peri s){ return x