#P10367. [2021年联测]Heavy Command Cruiser

    ID: 9485 传统题 5000ms 512MiB 尝试: 9 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS平面图对偶换根 DP转移矩阵转移矩阵乘积树上倍增长链剖分Disjoint Sparse TableLCA欧拉序ST 表

[2021年联测]Heavy Command Cruiser

题目描述

在平面上给定一棵有根树,树根为 11,根的深度为 00,其余节点的深度是其父亲的深度 +1+1。

对于深度为 xx 的节点,其 yy 坐标为 n−x+1n-x+1。

对于一个节点的所有子节点,xx 坐标从小到大按照编号升序排列。每条边都是一条连接两个点的线段。

每一个叶子节点都有一条平行于 yy 轴且向 yy 轴负方向无限延伸的射线,根节点有一条平行于 yy 轴且向 yy 轴正方向无限延伸的射线。

每个线段或射线带一个权值。

任意两条线段或射线只在树的节点处相交。

给定 qq 组 u,vu,v,你现在要从点 uu 开始在平面上自由移动,但是你不能经过除 u,vu,v 以外的任何树节点,且每经过一条线段或射线就会产生其对应的权值的代价。

你的目标是移动到点 vv,你需要求出移动过程产生的最小代价。

原题 PDF 中给出了一个示意图。图中的树以 11 为根,边为 (1,2),(1,3),(2,4),(2,5),(2,6),(3,7),(7,8),(7,9)(1,2),(1,3),(2,4),(2,5),(2,6),(3,7),(7,8),(7,9),所有边权均为 11。根有向上射线,叶子有向下射线。

输入格式

由于直接输入会造成巨大的输入量,所以本题采用特殊的输入方式。

给定如下随机数生成器:

namespace GenHelper
{
    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 GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

第一行三个整数 n,q,sn,q,s。在继续读入之前需要先调用一次 srand⁡(s)\operatorname{srand}(s)。

接下来 n−1n-1 行,每行两个整数,分别表示节点 i=2…ni=2\ldots n 在树上的父亲 fif_i 和其到父亲的边的权值 wiw_i。

接下来一个整数 w1w_1,表示节点 11 向上的射线的权值。

接下来一行若干个空格分隔的整数 dud_u,按照**叶子节点编号从小到大(注意不是在树上从左到右)**的顺序给出所有叶子节点向下的射线的权值。

接下来,对于每一组询问,设上一次询问的答案为 lastans\mathrm{lastans},如果这是第一次询问,则 lastans=0\mathrm{lastans}=0。你需要先调用一次 $(\operatorname{read}()\oplus\mathrm{lastans})\bmod n+1$ 得到询问的 uu,再调用一次 $(\operatorname{read}()\oplus\mathrm{lastans})\bmod n+1$ 得到询问的 vv。其中 ⊕\oplus 表示异或运算。

输出格式

输出两个空格分隔的整数,分别表示所有答案的异或和和所有答案的和。

样例

10 10 362881
1 1
2 1
3 7
4 2
3 10
5 10
7 3
3 10
2 8
7
4 1 5 5
2 6

样例 2

原题 PDF 引用了随比赛下发的样例 2,当前题目附件中只保留了题面和解题报告。

样例解释

1010 次询问分别为 $(2,2),(3,8),(9,10),(9,4),(6,1),(10,8),(10,6),(10,10),(6,1),(3,4)$,对应的答案分别为 0,0,0,1,1,1,2,0,1,00,0,0,1,1,1,2,0,1,0。

数据范围

对于 100%100\% 的数据,满足 1≤n≤3×1051\le n\le 3\times10^5,1≤q≤6×1061\le q\le 6\times10^6,1≤fi<i1\le f_i<i,1≤wi,w1,du≤2×1031\le w_i,w_1,d_u\le 2\times10^3,0≤s≤1090\le s\le10^9。

  • Subtask 1(3 pts):fi=i−1f_i=i-1。
  • Subtask 2(7 pts):fi=1f_i=1。
  • Subtask 3(11 pts):n,q≤500n,q\le500。
  • Subtask 4(27 pts):q=5×105q=5\times10^5,权值满足 w=1w=1。
  • Subtask 5(50 pts):q=5×105q=5\times10^5。
  • Subtask 6(2 pts):无特殊限制。