{"problem":{"name":"[JRKSJ R7] TSM eerT","description":{"content":"对于一个 $n$ 个结点的带边权的树 $T$，定义 $dis(x,y)$ 为 $T$ 中 $x\\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\\forall x,y\\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $dis(x,y)$。 定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8934"},"statements":[{"statement_type":"Markdown","content":"对于一个 $n$ 个结点的带边权的树 $T$，定义 $dis(x,y)$ 为 $T$ 中 $x\\to y$ 路径上的边权和。再定义一个 $n$ 个结点的无向完全图 $p(T)=G$，其中 $\\forall x,y\\in [1,n]$，$G$ 中边 $(x,y)$ 的边权为 $dis(x,y)$。\n\n定义 $f(T)$ 为 $p(T)$ 的最大生成树。特别的，若 $p(T)$ 的最大生成树不唯一，请立刻判断出并报告。\n\n给定树 $T_0$ 和整数 $k$，求 $f^k(T_0)$。其定义将在下文给出。\n\n## Input\n\n第一行两个整数 $n,k$。\\\n下面第 $2\\sim n$ 行，第 $i$ 行两个整数 $i-f_i,v_i$ 表示 $T_0$ 的一条边 $(i,f_i)$，边权为 $v_i$。**也就是说，这一行输入了两个整数 $f'_i,v_i$，真实的 $f_i=i-f'_i$。**\n\n## Output\n\n输出仅有一个整数表示答案。\n\n若 $\\exists x\\in[0,k-1]$ 使得 $p(f^x(T_0))$ 的最大生成树不唯一，输出 $-1$。否则，输出 $f^k(T_0)$ 的所有边权和对 $2^{32}$ 取模的结果。\n\n[samples]\n\n## Note\n\n### 定义\n\n$f^k(T)$ 的定义为：\n$$f^k(T)=\\begin{cases}T&k=0\\\\f(f^{k-1}(T))&k>0\\end{cases}$$\n\n### 样例 $1$ 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/fpcq3bmt.png)\n\n分别是 $T_0,f(T_0),f^2(T_0),f^3(T_0)$。\n\n以计算 $f(T_0)$ 的过程为例，生成的 $p(T_0)=G$ 为\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/3st5aet7.png)\n\n最大生成树上的边为 $(1,3),(2,3)$。\n\n### 数据规模\n\n本题采用捆绑测试。\n| $\\text{Subtask}$ | $n\\le$ | $k\\le$ | $\\text{Score}$ | \n| :----------: | :----------: | :----------: | :----------: | \n| $1$ | $10^3$ | $1$ | $10$ | \n| $2$ | $10^5$ | $1$ |$20$ |\n| $3$ | $10^6$ | $1$ |$30$ |\n| $4$ | $10^6$ | $10^7$ |$40$ |\n\n对于 $100\\%$ 的数据，$2\\le n\\le 10^6$，$1\\le k\\le 10^7$，$1\\le f_i