P7434 题解

· · 题解

定义 L_{x} 表示 x \rightarrow f_x 的左边的平面，R_x 同理。

首先我们考虑直击题目最核心的性质：给的是一颗树，而非图。联想到子树相关的 dp 不难发现，对于 L_x 而言，其到达 R_x 仅有三种形式：

1.经过 x \rightarrow f_x。

2.经过子树中的若干平面。

3.先经过 L_{f_x} 的左平面再经 R_{f_x} 再到达 R_x。

那么发现前两部分是独立的子树 dp（也可以理解为 floyd 松弛一部分边），可以 \mathcal O(n) 做，这里给出 dp 式子：w_{x}=min({w_{x},sum_{y \in son_x}w_y})。

然后再处理第三部分（原因是第三部分部分路径依赖于前两部分），同样的有：w_x=min(w_x,sum_{y \in son_{f_x}/x} w_x+w_{f_x})。（类似换根 dp ）。

处理出这一部分后，我们再次发掘 u \rightarrow v 路径的性质，也只有若干种情况，但是有一个共同的性质：一定会经过与 lca 相交的平面。

那么我们就可以处理 L_x/R_x 到若干级祖先的 L_{anc}/R_{anc} 的最短路，然后合并一下即可。

关于如何处理：

1.首先距离信息是一个半群，满足结合律（进一步的，可以写成矩阵的形式），所以可以进行倍增，复杂度 \mathcal O(n \log n+q \log n)，卡常后可通过本题，代码给的是这个实现。

2.我们也可以先 O(1) 求 LCA，仿照长链求 k 级祖先的方式，及先跳最大一步，在对应的长链上维护不超长链长度的向上 k 步的合并信息，直接合并即可。但对于链内，我们还需要 O(1) 求区间半群，做法有：猫树（预处理长链对于某个断点的前缀/后缀合并信息，然后询问时可以 O(1) 查分治树 LCA，也可以写成线段树，然后两个点的编号 xor 求 clz），sqrt tree。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=5e5+5;
int n,q,s,ans,lans,fa[N],fb[N],fc[N],fd[N],hd[N],nxt[N],pr[N],sum[N],mi[N],dep[N],f[N][19];
long long ans1;
struct ss{int x,y,z,w;}g[N][19];
struct ss1{int x,y;};
ss1 mul(const ss1 &x,const ss &y){return {min(x.x+y.x,x.y+y.z),min(x.x+y.y,x.y+y.w)};}
ss mul(const ss &x,const ss &y){return {min(x.x+y.x,x.y+y.z),min(x.x+y.y,x.y+y.w),min(x.z+y.x,x.w+y.z),min(x.z+y.y,x.w+y.w)};}
namespace sj{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_(){
        b=((z1<<6)^z1)>>13,z1=((z1&4294967294U)<<18)^b,b=((z2<<2)^z2)>>27,z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21,z3=((z3&4294967280U)<<7)^b,b=((z4<<3)^z4)>>12,z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
}
void srand(unsigned x){using namespace sj; z1=x,z2=(~x)^0x233333333U,z3=x^0x1234598766U,z4=(~x)+51;}
int read(){
    using namespace sj;
    int a=rand_()&32767,b=rand_()&32767;
    return a*32768+b;
}
int js(int x,int y){
    if(x==y) return 0;
    if(dep[x]<dep[y]) swap(x,y);
    ss1 dx={0,0},dy={0,0}; int jl=dep[x]-dep[y];
    if(jl>0){
        jl--;
        per(i,18,0) if((jl>>i)&1) dx=mul(dx,g[x][i]),x=f[x][i];
        if(fa[x]==y) return min(dx.x,dx.y);
        dx=mul(dx,g[x][0]),x=fa[x];
    }
    per(i,18,0) if(f[x][i]!=f[y][i]) dx=mul(dx,g[x][i]),x=f[x][i],dy=mul(dy,g[y][i]),y=f[y][i];
    if(x>y) swap(x,y),swap(dx,dy);
    int ans=dx.y+dy.x+sum[pr[y]]-sum[x];
    dx=mul(dx,g[x][0]),dy=mul(dy,g[y][0]);
    return min(ans,dx.x+dy.y+mi[fa[x]]);
}  
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>q>>s,srand(s);
    rep(i,2,n) cin>>fa[i]>>fb[i];
    per(i,n,2){
        if(hd[fa[i]]) pr[hd[fa[i]]]=i;
        nxt[i]=hd[fa[i]],hd[fa[i]]=i;
    }cin>>fb[1];
    rep(i,1,n) if(!hd[i]) cin>>fc[i];
    per(i,n,1) if(hd[i]){
        int lst=0;
        for(int j=hd[i];j;lst=j,j=nxt[j]) sum[j]=sum[pr[j]]+min(fb[j],fc[j]);
        fc[i]=sum[lst];
    }mi[1]=fb[1];
    rep(i,2,n){
        dep[i]=dep[fa[i]]+1,f[i][0]=fa[i]; int dq=min(fb[fa[i]],fc[fa[i]]);
        g[i][0]={sum[pr[i]],fc[fa[i]]-sum[pr[i]],sum[i],fc[fa[i]]-sum[i]};
        g[i][0].x=min(g[i][0].x,g[i][0].y+dq),g[i][0].y=min(g[i][0].y,g[i][0].x+dq);
        g[i][0].z=min(g[i][0].z,g[i][0].w+dq),g[i][0].w=min(g[i][0].w,g[i][0].z+dq);
        mi[i]=min({mi[fa[i]]+g[i][0].x+g[i][0].w,fb[i],fc[i]});
    }
    rep(j,1,18) rep(i,1,n) if(dep[i]>=(1<<j)) f[i][j]=f[f[i][j-1]][j-1],g[i][j]=mul(g[i][j-1],g[f[i][j-1]][j-1]);
    while(q--){int x=(read()^lans)%n+1,y=(read()^lans)%n+1; lans=js(x,y),ans^=lans,ans1+=lans;}
    cout<<ans<<" "<<ans1;
}