[luogu7434]Heavy Command Cruiser

对于叶子$x$，注意到$x$向下的射线仅是用于划分区域，其权值$d_{x}$可以直接记在$w_{x}$上（取$\min$）

定义$w'_{x}$为$x$向上的边（特别的，$x=1$时即1向上的射线）两侧的区域在对偶图中的最短路，考虑如何求——

称某区域在$x$的子树内当且仅当其相邻的两个叶子均在$x$子树内，并对路径分类讨论：

1.路径经过的区域（除起点和终点外）均在$x$子树内，这种情况的转移即$w'_{x}=\min(\sum_{son是x的儿子}w'_{son},w_{x})$

2.路径经过的区域均不在$x$子树内，这种情况的转移即$w'_{x}=\min(\sum_{bro是x的兄弟}w'_{bro}+w'_{fa_{x}},w'_{x})$

进一步的，不妨用$w'_{x}$代替$w_{x}$，进而即区域间的最短路经过相邻的区域必然直接使用对应的边

回到原问题，结合上述性质，不难发现经过的所有区域均是$u$到$v$路径上两侧的区域

令$f_{k,i,0/1,0/1}$表示从$k$向上的边左/右侧到$k$的$2^{i}$次祖先向上的边左/右侧的最短路，即可倍增转移

由于询问次数较多，需要通过长链剖分+sqrt tree做到$o(n\log n+q)$

（下面的代码并没有做上述优化，仅能得到20分）

  1 #include
  2 using namespace std;
  3 #define N 500005
  4 #define ll long long
  5 struct Data{
  6     int a[2][2];
  7     Data(int p=0x3f3f3f3f){
  8         a[0][0]=a[0][1]=a[1][0]=a[1][1]=p;
  9     }
 10     int get_min(){
 11         return min(min(a[0][0],a[0][1]),min(a[1][0],a[1][1]));
 12     }
 13 }f[N][20];
 14 vector<int>v[N];
 15 int n,q,x,y,ans,ans1,w[N],dep[N],sum[N],fa[N][20];
 16 ll ans2;
 17 namespace GenHelper{
 18     unsigned z1,z2,z3,z4,b;
 19     unsigned rand_(){
 20         b=((z1<<6)^z1)>>13;
 21         z1=((z1&4294967294U)<<18)^b;
 22         b=((z2<<2)^z2)>>27;
 23         z2=((z2&4294967288U)<<2)^b;
 24         b=((z3<<13)^z3)>>21;
 25         z3=((z3&4294967280U)<<7)^b;
 26         b=((z4<<3)^z4)>>12;
 27         z4=((z4&4294967168U)<<13)^b;
 28         return (z1^z2^z3^z4);
 29     }
 30 };
 31 void srand(unsigned x){
 32     using namespace GenHelper;
 33     z1=x;z2=(~x)^0x233333333U;z3=x^0x1234598766U;z4=(~x)+51;
 34 }
 35 int Read(){
 36     using namespace GenHelper;
 37     int a=rand_()&32767;
 38     int b=rand_()&32767;
 39     return a*32768+b;
 40 }
 41 int read(){
 42     int x=0;
 43     char c=getchar();
 44     while ((c<'0')||(c>'9'))c=getchar();
 45     while ((c>='0')&&(c<='9')){
 46         x=x*10+c-'0';
 47         c=getchar();
 48     }
 49     return x;
 50 }
 51 Data merge(Data x,Data y){
 52     Data ans;
 53     ans.a[0][0]=min(x.a[0][0]+y.a[0][0],x.a[0][1]+y.a[1][0]);
 54     ans.a[0][1]=min(x.a[0][0]+y.a[0][1],x.a[0][1]+y.a[1][1]);
 55     ans.a[1][0]=min(x.a[1][0]+y.a[0][0],x.a[1][1]+y.a[1][0]);
 56     ans.a[1][1]=min(x.a[1][0]+y.a[0][1],x.a[1][1]+y.a[1][1]);
 57     return ans;
 58 }
 59 void dfs1(int k){
 60     int s=0;
 61     for(int i=0;iw[v[k][i]];
 62     if (!v[k].empty())w[k]=min(w[k],s);
 63 }
 64 void dfs2(int k){
 65     int s=w[k];
 66     for(int i=0;iw[v[k][i]];
 67     for(int i=0;i){
 68         w[v[k][i]]=min(w[v[k][i]],s-w[v[k][i]]);
 69         dfs2(v[k][i]);
 70     }
 71 }
 72 void dfs(int k,int s){
 73     dep[k]=s;
 74     for(int i=1;i<20;i++){
 75         fa[k][i]=fa[fa[k][i-1]][i-1];
 76         f[k][i]=merge(f[k][i-1],f[fa[k][i-1]][i-1]);
 77     }
 78     if (v[k].empty())return;
 79     sum[v[k][0]]=w[v[k][0]];
 80     for(int i=1;i1]]+w[v[k][i]];
 81     for(int i=0;i){
 82         int l=0,r=sum[v[k].back()]-sum[v[k][i]];
 83         if (i)l=sum[v[k][i-1]];
 84         f[v[k][i]][0].a[0][0]=min(l,r+w[v[k][i]]+w[k]);
 85         f[v[k][i]][0].a[0][1]=min(l+w[k],r+w[v[k][i]]);
 86         f[v[k][i]][0].a[1][0]=min(l+w[v[k][i]],r+w[k]);
 87         f[v[k][i]][0].a[1][1]=min(l+w[v[k][i]]+w[k],r);
 88         dfs(v[k][i],s+1);
 89     }
 90 }
 91 int calc(int x,int y){
 92     if (x==y)return 0;
 93     if (dep[x]<dep[y])swap(x,y);
 94     Data ans1(0),ans2(0);
 95     ans1.a[0][1]=ans1.a[1][0]=w[x];
 96     ans2.a[0][1]=ans2.a[1][0]=w[y];
 97     for(int i=19;i>=0;i--)
 98         if (dep[fa[x][i]]>dep[y]){
 99             ans1=merge(ans1,f[x][i]);
100             x=fa[x][i];
101         }
102     if (fa[x][0]==y)return ans1.get_min();
103     if (dep[x]>dep[y])ans1=merge(ans1,f[x][0]),x=fa[x][0];
104     for(int i=19;i>=0;i--)
105         if (fa[x][i]!=fa[y][i]){
106             ans1=merge(ans1,f[x][i]),ans2=merge(ans2,f[y][i]);
107             x=fa[x][i],y=fa[y][i];
108         }
109     if (x>y)swap(x,y),swap(ans1,ans2);
110     int z=fa[x][0],S=w[z]+sum[v[z].back()];
111     int lx=min(ans1.a[0][0],ans1.a[1][0]),rx=min(ans1.a[0][1],ans1.a[1][1]);
112     int ly=min(ans2.a[0][0],ans2.a[1][0]),ry=min(ans2.a[0][1],ans2.a[1][1]);
113     return min(lx+ry+S-(sum[y]-sum[x]+w[x]),ly+rx+(sum[y]-sum[x]-w[y]));
114 }
115 int main(){
116     n=read(),q=read(),srand(read());
117     for(int i=2;i<=n;i++){
118         x=read(),w[i]=read();
119         fa[i][0]=x,v[x].push_back(i);
120     }
121     w[1]=read();
122     for(int i=1;i<=n;i++)
123         if (v[i].empty())w[i]=min(w[i],read());
124     dfs1(1),dfs2(1),dfs(1,1);
125     for(int i=1;i<=q;i++){
126         x=(Read()^ans)%n+1,y=(Read()^ans)%n+1;
127         ans=calc(x,y),ans1^=ans,ans2+=ans;
128     }
129     printf("%d %lld\n",ans1,ans2);
130     return 0;
131 }