「比赛总结」正睿 提高十连 Day1

📅 Last Updated: 2020-08-31
📊 Word Count: 1523
⏱️ Estimated Reading Time: 10 minutes
📄 PDF 📝 Source

2020 第一次正睿提高十连测，题目很妙。

Problems

A

将 nn 个石子分成 xx 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ (k≤1)(k \le 1)。最小化 xx 输出 xx。

n≤1011n \le 10^{11}

B

给出一个字符串 SS ，求出字符串中，有多少连续的子串形如 AArAA A_r A 。

其中 ArA_r 表示 AA 的反串。合法的相同字串出现多次，统计多次。

∣S∣≤2×106|S| \le 2 \times 10^6

C

给出一个 nn 个点的树（保证这棵树随机生成），点有点权， 规定 11 号点为根节点。

随机生成一个 nn 排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 xx 时，需要将包括 xx 在内的所有 xx 子树中的点的点权 VV 加上 xx 点的当前权值 Vx′V^{'}_x。

求出最终所有点权和的期望值。

n≤105n \le 10^5

Problem A Stone

Statement

将 nn 个石子分成 xx 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ (k≤1)(k \le 1)。最小化 xx 输出 xx。

n≤1011n \le 10^11

Analysis

引理 1

对于任意一个正整数 xx， 均可以被拆分为 33 个形如 (n2)\dbinom{n}{2} 的数字。

引理 2

可以证明 xx 一定小于等于 88。

证明 引理 2

我们需要的数字是 3k2−3k+1=6×n(n+1)2+1=6×(n2)+13k^2 - 3k + 1 = 6 \times \dfrac{n (n + 1)}{2} + 1 = 6 \times \dbinom{n}{2} + 1.

考虑一定存在 N−kN - k 是 66 的倍数。 所以 N−k+3N - k + 3 必然可以写成 三个形如 3k2−3k+13k^2 - 3k + 1 数的和的形式.

而 N−k+3N - k + 3 最多和 NN 相差 55 所以最多补 55 个 11 就可以凑出 NN.

引理 3

ans≡N  (mod  6)ans \equiv N\ \ (mod\ \ 6)

证明 引理 3

因为 ∑3k2−3k+1=∑6×n(n+1)2+1=∑6×(n2)+1\sum 3k^2 - 3k + 1 = \sum 6 \times \dfrac{n (n + 1)}{2} + 1 = \sum 6 \times \dbinom{n}{2} + 1.

显然 ∑6×(n2)+1≡1  (mod  6)\sum 6 \times \dbinom{n}{2} + 1 \equiv 1\ \ (mod\ \ 6).

易知 ans≡N  (mod  6)ans \equiv N\ \ (mod\ \ 6)

只需要判断答案是 11 还是 77， 是 22 还是 88。 - 判断是否为 11 直接判断即可。 - 判断是否为 22 双指针扫一遍即可。

Problem B Palindrome

Statement

给出一个字符串，求出字符串中，有多少连续的子串形如 AArAA A_r A 。

其中 ArA_r 表示 AA 的反串。合法的相同字串出现多次，统计多次。

∣S∣≤2×106|S| \le 2 \times 10^6

Analysis

先用各种神奇的算法（字符串 Hash 、manacher）求出 len[i] 表示第 ii 个字符和第 i+1i + 1 个字符之间为中心，向两边扩展最长的回文串.

枚举 AArAA A_r A 的 13\frac{1}{3} 位置 ii ，在 [i+1,i+len[i]][i + 1, i + \text{len}[i]] 这个区间中有多少 xx 满足 x−len[x]≤ix - \text{len}[x] \le i， 每一个合法的 xx 给答案贡献 11.

转化为 问题.

可以采用 或者 后采用 扫描.

Problem C Random

给出一个 nn 个点的树（保证这棵树随机生成），点有点权， 规定 11 号点为根节点。

随机生成一个 nn 排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 xx 时，需要将包括 xx 在内的所有 xx 子树中的点，点权加 VxV_x。

n≤105n \le 10^5

关于期望思考

期望的 ：标志着很多情况下的期望可以分开算，算完后再合并。例如：点权和的期望 == 点权的期望和。

直观感受一下：期望是一个随机变量的平均情况下的数值。

我们不知道这个随机变量xx确切的数值，自然也不知道由这个随机变量推导出来的另一个随机变量XX（例如：如果我们不知道 每个点 操作后的 确切点权，那么所有点的点权和的确切数值也无从得知。）

但是如果我们知道每个点在 下取到的值xx，我们一样可以通过随机变量xx 下取到的值推出XX在 下取到的值。

关于本题，我们同样可以拆开来看，要求 求出结点的期望和，那我们可以求出每个点的期望权值，然后再相加就能得到所有结点的期望和。

对于一个有根树上的每一个结点，可能能对这个结点的权值产生贡献的 它的祖先。

这个点 aa 最终权值的期望 Va′V^{'}_a 就是点 aa 的初始权值和所有 aa 的祖先对点 aa 的期望贡献之和。

aa 的祖先 pp 对 aa 的期望贡献可以拆成 Vp′V^{'}_p 与 对 aa 的贡献次数的乘积。

对于每一条树链上的任意一个点 xx 来说某一个祖先 pp 对其贡献的次数，只与这个祖先pp和这个点xx的距离有关。

不妨定义 dp[i]\text{dp}[i] 为结点 11 到往下的第 ii 个点的期望贡献次数（ ：第 11 个点对第 11 个点的贡献次数定义为 dp[1]\text{dp}[1] ）。

对于每一条树链，我们都可以采用同一套 dp\text{dp} 值进行处理，因为对于每个点来说，其祖先的对其贡献次数只与他们之间的相对位置有关。

考虑如何预处理出 dp[i]\text{dp}[i]：

考虑结点 11 如何对其往下第 i−1i - 1 结点 xx 产生贡献。（不妨设：这一条树链上结点的编号由 依次为 1−k1-k ）。

考虑贡献的传递过程，结点 11 的贡献传给 xx 有两种情况：

  • 由 11 直接传递给 xx

  • 由 11 传递给 xx 的中间的若干结点，经过多次传递后传递给 xx 。

这些方案对应的贡献为 11 ，所以只要求出方案数量，就可以求出结点 11 对 xx 的贡献次数。

考虑这些方案对应着什么—— nn 的排列中 以 11 开始的上升序列的个数。

于是，dp[i]\text{dp}[i] 就等于在 nn 的排列中 以 11 开始的上升序列的个数。

枚举一个上升序列的长度 dd ，统计其数量即可

dp[i]=∑d=1i(i−1d−1)×(id)×(i−d)! \text{dp}[i] = \sum_{d = 1}^{i} \dbinom{i - 1}{d - 1} \times \dbinom{i}{d} \times (i - d)!

其中： - (i−1d−1)\dbinom{i - 1}{d - 1} 指在 i−1i - 1 中选定 d−1d - 1 个数字 。

  • (id)\dbinom{i}{d} 指在 ii 个位置中选 dd 个将这 dd 个数字放下。

  • (i−d)!(i - d)! 指 剩下的(i−d)(i - d)个位置的数字任意排列。

最后需要注意一点，因为树是随机生成的，其实这就保证了树的高度（树链的最长长度）在O(n)O(\sqrt n)级别，预处理和统计答案相当于是线性的。

Codes

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int _ = 1e7 + 100;
#define LL long long 
LL read(){ LL x; scanf("%lld", &x); return x; }
LL A[_], Q;
void init(){
    for(int i = 1; ; i++) { A[i] = ( (i) *1ll* (i - 1) ) >> 1; if(A[i] > 1e11) break; else Q = i; }
}
int doit(LL x){
    if(x % 6 != 1 && x % 6 != 2) return x % 6 == 0 ? 6 : x % 6;
    if(x % 6 == 1){
        x = (x - 1) / 6;
        if( ( *lower_bound(A + 1, A + Q + 1, x) ) == ( x ) ) return 1;
        else return 7;
    } else {
        x = (x - 2) / 6;
        int L = 1, R = Q;
        while(L <= R){
            if(A[L] + A[R] == x) return 2;
            while(A[R] + A[L] < x) L++;
            while(A[R] + A[L] > x) R--;
        }
        return 8;
    }
}
int main(){
    int T = read();
    init();
    while(T--) printf("%d\n", doit(read()));
    return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <ctime>
#include <algorithm>
using namespace std;
const int _ = 2e7 + 100;
#define LL long long 
int read(){ int x; scanf("%d", &x); return x; }
char S[_];
int  n;
namespace Hash{
    const int MOD  = 998244353;
    const int base = 'z' + 10;
    int ahs[_];
    int bhs[_];
    int POW[_];
    int pow(int a, int b, int p){ int ans = 1; while(b) { if(b & 1) ans = (ans *1LL* a) % p; a = (a *1ll* a) % p; b >>= 1; } return ans; }
    int suba(int L, int R) { return (  ahs[R] - (ahs[L - 1] *1ll* POW[R - L + 1] % MOD)  +0ll+ MOD) % MOD; }
    int subb(int L, int R) { return (  bhs[L] - (bhs[R + 1] *1ll* POW[R - L + 1] % MOD)  +0ll+ MOD) % MOD; }
    void initHash(int x){
        POW[0] = 1;
        for(int i = 1; i <= x; i++) POW[i] = POW[i - 1] *1ll* base % MOD;
        for(int i = 1; i <= x; i++){
            ahs[i] = ( (ahs[i - 1] *1ll* base) +0ll+ S[i] ) % MOD;
        }
        for(int i = x; i >= 1; i--){
            bhs[i] = ( (bhs[i + 1] *1ll* base) +0ll+ S[i] ) % MOD;
        }
    }
}
using Hash::initHash;
using Hash::suba;
using Hash::subb;
int mlen[_];
int qury[_];

int main(){
    clock_t t0 = clock();
    freopen("in.txt", "r", stdin);
    scanf("%s", S + 1); n = strlen(S + 1);
    initHash(n);
    for(int i = 1; i < n; i++){
        if(S[i] != S[i + 1]) { mlen[i] = 0; continue; }
        int L = 0;
        int R = i;
        int ans = 0;
        while(L < R){
            int mid = L + ((R - L + 1) >> 1);
            if(suba(i - mid + 1, i) == subb(i + 1, i + mid)) ans = mid, L = mid;
            else R = mid - 1;
        }
        mlen[i] = ans;
    }

    for(int i = 1; i < n; i++) qury[i] = i - mlen[i];

    int ans = 0;
    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= i + mlen[i];j++) ans += (j - mlen[j] <= i);
    }
    printf("%d", ans);
    return 0;
}
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <iostream>
#define MOD 1000000007
using namespace std;
int read(){ int x; scanf("%d", &x); return x; }
const int _ = 1e5 + 100;
const int MAXD = 1e3 + 100;
int head[_];
struct edges{
    int node;
    int nxt;
}edge[_ << 1];
int tot = 0;
void add(int u, int v){
    tot++;
    edge[tot].node = v;
    edge[tot].nxt  = head[u];
    head[u]        = tot;
}
int n;
int rt = 1;
int C[MAXD + 100][MAXD + 100];
int frc[_];
int dp[_];
int pow(int a, int b, int P)  { int ans = 1; while(b) { if(b & 1) ans = (ans *1ll* a) % P; a = (a *1ll* a) % P; b >>= 1; } return ans; }
int inv(int x){ return pow(x, MOD - 2, MOD); }
const int DB = 20;
void init(){
    C[0][0] = 1;
    for(int i = 1; i <= MAXD; i++){
        C[i][0] = 1;
        for(int j = 1; j <= i; j++){
            C[i][j] = ( C[i - 1][j] +0ll+ C[i - 1][j - 1] ) % MOD;
        }
    }
    frc[0] = 1;
    for(int i = 1; i <= _ - 10; i++) frc[i] = ( frc[i - 1] *1ll* (i) ) % MOD;
    for(int i = 1; i <= MAXD; i++){
        dp[i] = 0;
        for(int d = 1; d <= i; d++){
            dp[i] = (dp[i] +0ll+ (
                (  ( (C[i - 1][d - 1] *1ll* C[i][d]) % MOD ) *1ll* frc[i - d]  ) % MOD
                    ) % MOD) % MOD;
        }
    }
    for(int i = 1; i <= MAXD; i++) dp[i] = (dp[i] *1ll* inv(frc[i])) % MOD;
}
int ans = 0;
struct Stack{ int v[_]; int top; Stack(){ top = 0; } inline int *GetHead(){ return &v[0]; } inline int* GetTail(){ return &v[top]; } void push(int x){v[top++] = x;} void pop(){top --;} };
Stack S;
int val[_];
int NodeVal[_];
void dfs0(int o, int fa, int dep){
    S.push(o);
    int now = dep;
    for(int *i = S.GetHead(); i != S.GetTail(); i++){
        val[o] = (  val[o] +0ll+ (dp[now] *1ll* NodeVal[*i]) % MOD  ) % MOD;
        now --;
    }
    for(int i = head[o]; i ; i = edge[i].nxt){
        int ex = edge[i].node;
        if(ex == fa) continue;
        dfs0(ex, o, dep + 1);
    }
    S.pop();
}
int main(){
    n = read();
    init();
    for(int i = 1; i < n; i++){ int u = read(), v = read(); add(u, v); add(v, u); }
    for(int i = 1; i <= n; i++) NodeVal[i] = read();
    dfs0(1, -1, 1);
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = (ans +0ll+ NodeVal[i]) % MOD;
    for(int i = 1; i <= n; i++) ans = (ans +0ll+ val[i]) % MOD;
    printf("%d\n", (ans *1ll* frc[n]) % MOD);
    return 0;
}

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 191315f27444e78b11b5afc47204f6d1fe79feff79992e9ab61495dbe0edbb09
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「比赛总结」「ZROI-2020-十连测」Day1.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「比赛总结」「ZROI-2020-十连测」Day1.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../a6e59bc13a.pdf.md', '-o', 'cache/a6e59bc13a.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「比赛总结」正睿 提高十连 Day1},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「比赛总结」正睿 提高十连 Day1}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-08-31 08:21:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  2020 第一次正睿提高十连测，题目很妙。
  
  \subsection{Problems}\label{problems}
  
  \paragraph{A}\label{a}
  
  将 \(n\) 个石子分成 \(x\) 堆，使每一堆的石子个数都形如 \$ 3k\^{}2 - 3k +
  1\$ \((k \le 1)\)。最小化 \(x\) 输出 \(x\)。
  
  \(n \le 10^{11}\)
  
  \paragraph{B}\label{b}
  
  给出一个字符串 \(S\) ，求出字符串中，有多少连续的子串形如 \(A A_r A\) 。
  
  其中 \(A_r\) 表示 \(A\) 的反串。合法的相同字串出现多次，统计多次。
  
  \(|S| \le 2 \times 10^6\)
  
  \paragraph{C}\label{c}
  
  给出一个 \(n\) 个点的树（保证这棵树\textbf{随机生成}），点有点权， 规定
  \(1\) 号点为根节点。
  
  \textbf{随机}生成一个 \(n\)
  排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 \(x\)
  时，需要将包括 \(x\) 在内的所有 \(x\) 子树中的点的点权 \(V\) 加上 \(x\)
  点的当前权值 \(V^{'}_x\)。
  
  求出最终所有点权和的期望值。
  
  \(n \le 10^5\)
  
  \subsection{Problem A Stone}\label{problem-a-stone}
  
  \subsubsection{Statement}\label{statement}
  
  将 \(n\) 个石子分成 \(x\) 堆，使每一堆的石子个数都形如 \$ 3k\^{}2 - 3k +
  1\$ \((k \le 1)\)。最小化 \(x\) 输出 \(x\)。
  
  \(n \le 10^11\)
  
  \subsubsection{Analysis}\label{analysis}
  
  \paragraph{引理 1}\label{ux5f15ux7406-1}
  
  对于任意一个正整数 \(x\)， 均可以被拆分为 \(3\) 个形如 \(\dbinom{n}{2}\)
  的数字。
  
  \paragraph{引理 2}\label{ux5f15ux7406-2}
  
  可以证明 \(x\) 一定小于等于 \(8\)。
  
  \paragraph{证明 引理 2}\label{ux8bc1ux660e-ux5f15ux7406-2}
  
  我们需要的数字是
  \(3k^2 - 3k + 1 = 6 \times \dfrac{n (n + 1)}{2} + 1 = 6 \times \dbinom{n}{2} + 1\).
  
  考虑一定存在 \(N - k\) 是 \(6\) 的倍数。 所以 \(N - k + 3\) 必然可以写成
  三个形如 \(3k^2 - 3k + 1\) 数的和的形式.
  
  而 \(N - k + 3\) 最多和 \(N\) 相差 \(5\) 所以最多补 \(5\) 个 \(1\)
  就可以凑出 \(N\).
  
  \paragraph{引理 3}\label{ux5f15ux7406-3}
  
  \(ans \equiv N\ \ (mod\ \ 6)\)
  
  \paragraph{证明 引理 3}\label{ux8bc1ux660e-ux5f15ux7406-3}
  
  因为
  \(\sum 3k^2 - 3k + 1 = \sum 6 \times \dfrac{n (n + 1)}{2} + 1 = \sum 6 \times \dbinom{n}{2} + 1\).
  
  显然 \(\sum 6 \times \dbinom{n}{2} + 1 \equiv 1\ \ (mod\ \ 6)\).
  
  易知 \(ans \equiv N\ \ (mod\ \ 6)\)
  
  只需要判断答案是 \(1\) 还是 \(7\)， 是 \(2\) 还是 \(8\)。 - 判断是否为
  \(1\) 直接判断即可。 - 判断是否为 \(2\) 双指针扫一遍即可。
  
  \subsection{Problem B Palindrome}\label{problem-b-palindrome}
  
  \subsubsection{Statement}\label{statement-1}
  
  给出一个字符串，求出字符串中，有多少连续的子串形如 \(A A_r A\) 。
  
  其中 \(A_r\) 表示 \(A\) 的反串。合法的相同字串出现多次，统计多次。
  
  \(|S| \le 2 \times 10^6\)
  
  \subsubsection{Analysis}\label{analysis-1}
  
  先用各种神奇的算法（\texttt{字符串\ Hash} 、\texttt{manacher}）求出
  \texttt{len{[}i{]}} 表示第 \(i\) 个字符和第 \(i + 1\)
  个字符之间为中心，向两边扩展最长的回文串.
  
  枚举 \(A A_r A\) 的 \(\frac{1}{3}\) 位置 \(i\) ，在
  \([i + 1, i + \text{len}[i]]\) 这个区间中有多少 \(x\) 满足
  \(x - \text{len}[x] \le i\)， 每一个合法的 \(x\) 给答案贡献 \(1\).
  
  转化为 问题.
  
  可以采用 或者 后采用 扫描.
  
  \subsection{Problem C Random}\label{problem-c-random}
  
  给出一个 \(n\) 个点的树（保证这棵树\textbf{随机生成}），点有点权， 规定
  \(1\) 号点为根节点。
  
  \textbf{随机}生成一个 \(n\)
  排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 \(x\)
  时，需要将包括 \(x\) 在内的所有 \(x\) 子树中的点，点权加 \(V_x\)。
  
  \(n \le 10^5\)
  
  \paragraph{关于期望思考}\label{ux5173ux4e8eux671fux671bux601dux8003}
  
  期望的
  ：标志着很多情况下的期望可以分开算，算完后再合并。例如：点权和的期望
  \(=\) 点权的期望和。
  
  直观感受一下：期望是一个随机变量的平均情况下的数值。
  
  我们不知道这个随机变量\(x\)确切的数值，自然也不知道由这个随机变量推导出来的另一个随机变量\(X\)（例如：如果我们不知道
  每个点 操作后的
  \textbf{确切点权}，那么所有点的点权和的\textbf{确切数值}也无从得知。）
  
  但是如果我们知道每个点在 下取到的值\(x\)，我们一样可以通过随机变量\(x\)
  下取到的值推出\(X\)在 下取到的值。
  
  关于本题，我们同样可以拆开来看，要求
  求出结点的期望和，那我们可以求出每个点的期望权值，然后再相加就能得到所有结点的期望和。
  
  对于一个有根树上的每一个结点，可能能对这个结点的权值产生贡献的
  它的祖先。
  
  这个点 \(a\) 最终权值的期望 \(V^{'}_a\) 就是点 \(a\) 的初始权值和所有
  \(a\) 的祖先对点 \(a\) 的期望贡献之和。
  
  \(a\) 的祖先 \(p\) 对 \(a\) 的期望贡献可以拆成 \(V^{'}_p\) 与 对 \(a\)
  的贡献次数的乘积。
  
  对于每一条树链上的任意一个点 \(x\) 来说某一个祖先 \(p\)
  对其贡献的次数，只与这个祖先\(p\)和这个点\(x\)的距离有关。
  
  不妨定义 \(\text{dp}[i]\) 为结点 \(1\) 到往下的第 \(i\)
  个点的期望贡献次数（ ：第 \(1\) 个点对第 \(1\) 个点的贡献次数定义为
  \(\text{dp}[1]\) ）。
  
  对于每一条树链，我们都可以采用同一套 \(\text{dp}\)
  值进行处理，因为对于每个点来说，其祖先的对其贡献次数只与他们之间的相对位置有关。
  
  考虑如何预处理出 \(\text{dp}[i]\)：
  
  考虑结点 \(1\) 如何对其往下第 \(i - 1\) 结点 \(x\)
  产生贡献。（不妨设：这一条树链上结点的编号由 依次为 \(1-k\) ）。
  
  考虑贡献的传递过程，结点 \(1\) 的贡献传给 \(x\) 有两种情况：
  
  \begin{itemize}
  \item
    由 \(1\) 直接传递给 \(x\)
  \item
    由 \(1\) 传递给 \(x\) 的中间的若干结点，经过多次传递后传递给 \(x\) 。
  \end{itemize}
  
  这些方案对应的贡献为 \(1\) ，所以只要求出方案数量，就可以求出结点 \(1\)
  对 \(x\) 的贡献次数。
  
  考虑这些方案对应着什么—— \(n\) 的排列中 以 \(1\)
  开始的\textbf{上升序列}的个数。
  
  于是，\(\text{dp}[i]\) 就等于在 \(n\) 的排列中 以 \(1\)
  开始的\textbf{上升序列}的个数。
  
  枚举一个上升序列的长度 \(d\) ，统计其数量即可
  
  \[ \text{dp}[i] = \sum_{d = 1}^{i} \dbinom{i - 1}{d - 1} \times \dbinom{i}{d} \times (i - d)! \]
  
  其中： - \(\dbinom{i - 1}{d - 1}\) 指在 \(i - 1\) 中选定 \(d - 1\)
  个数字 。
  
  \begin{itemize}
  \item
    \(\dbinom{i}{d}\) 指在 \(i\) 个位置中选 \(d\) 个将这 \(d\)
    个数字放下。
  \item
    \((i - d)!\) 指 剩下的\((i - d)\)个位置的数字任意排列。
  \end{itemize}
  
  最后需要注意一点，因为树是随机生成的，其实这就保证了树的高度（树链的最长长度）在\(O(\sqrt n)\)级别，预处理和统计答案相当于是线性的。
  
  \subsection{Codes}\label{codes}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e7} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \PreprocessorTok{\#define LL }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \NormalTok{LL read}\OperatorTok{()\{}\NormalTok{ LL x}\OperatorTok{;}\NormalTok{ scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%lld}\StringTok{"}\OperatorTok{,} \OperatorTok{\&}\NormalTok{x}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;} \OperatorTok{\}}
  \NormalTok{LL A}\OperatorTok{[}\NormalTok{\_}\OperatorTok{],}\NormalTok{ Q}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ init}\OperatorTok{()\{}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \OperatorTok{;}\NormalTok{ i}\OperatorTok{++)} \OperatorTok{\{}\NormalTok{ A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(} \OperatorTok{(}\NormalTok{i}\OperatorTok{)} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*} \OperatorTok{(}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{)} \OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\textgreater{}} \FloatTok{1e11}\OperatorTok{)} \ControlFlowTok{break}\OperatorTok{;} \ControlFlowTok{else}\NormalTok{ Q }\OperatorTok{=}\NormalTok{ i}\OperatorTok{;} \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ doit}\OperatorTok{(}\NormalTok{LL x}\OperatorTok{)\{}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{\%} \DecValTok{6} \OperatorTok{!=} \DecValTok{1} \OperatorTok{\&\&}\NormalTok{ x }\OperatorTok{\%} \DecValTok{6} \OperatorTok{!=} \DecValTok{2}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{\%} \DecValTok{6} \OperatorTok{==} \DecValTok{0} \OperatorTok{?} \DecValTok{6} \OperatorTok{:}\NormalTok{ x }\OperatorTok{\%} \DecValTok{6}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{\%} \DecValTok{6} \OperatorTok{==} \DecValTok{1}\OperatorTok{)\{}
  \NormalTok{        x }\OperatorTok{=} \OperatorTok{(}\NormalTok{x }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{)} \OperatorTok{/} \DecValTok{6}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(} \OperatorTok{(} \OperatorTok{*}\NormalTok{lower\_bound}\OperatorTok{(}\NormalTok{A }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ A }\OperatorTok{+}\NormalTok{ Q }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ x}\OperatorTok{)} \OperatorTok{)} \OperatorTok{==} \OperatorTok{(}\NormalTok{ x }\OperatorTok{)} \OperatorTok{)} \ControlFlowTok{return} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{else} \ControlFlowTok{return} \DecValTok{7}\OperatorTok{;}
      \OperatorTok{\}} \ControlFlowTok{else} \OperatorTok{\{}
  \NormalTok{        x }\OperatorTok{=} \OperatorTok{(}\NormalTok{x }\OperatorTok{{-}} \DecValTok{2}\OperatorTok{)} \OperatorTok{/} \DecValTok{6}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ L }\OperatorTok{=} \DecValTok{1}\OperatorTok{,}\NormalTok{ R }\OperatorTok{=}\NormalTok{ Q}\OperatorTok{;}
          \ControlFlowTok{while}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}=}\NormalTok{ R}\OperatorTok{)\{}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{L}\OperatorTok{]} \OperatorTok{+}\NormalTok{ A}\OperatorTok{[}\NormalTok{R}\OperatorTok{]} \OperatorTok{==}\NormalTok{ x}\OperatorTok{)} \ControlFlowTok{return} \DecValTok{2}\OperatorTok{;}
              \ControlFlowTok{while}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{R}\OperatorTok{]} \OperatorTok{+}\NormalTok{ A}\OperatorTok{[}\NormalTok{L}\OperatorTok{]} \OperatorTok{\textless{}}\NormalTok{ x}\OperatorTok{)}\NormalTok{ L}\OperatorTok{++;}
              \ControlFlowTok{while}\OperatorTok{(}\NormalTok{A}\OperatorTok{[}\NormalTok{R}\OperatorTok{]} \OperatorTok{+}\NormalTok{ A}\OperatorTok{[}\NormalTok{L}\OperatorTok{]} \OperatorTok{\textgreater{}}\NormalTok{ x}\OperatorTok{)}\NormalTok{ R}\OperatorTok{{-}{-};}
          \OperatorTok{\}}
          \ControlFlowTok{return} \DecValTok{8}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
      \DataTypeTok{int}\NormalTok{ T }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    init}\OperatorTok{();}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{T}\OperatorTok{{-}{-})}\NormalTok{ printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ doit}\OperatorTok{(}\NormalTok{read}\OperatorTok{()));}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}ctime\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}algorithm\textgreater{}}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{2e7} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \PreprocessorTok{\#define LL }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{;}\NormalTok{ scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,} \OperatorTok{\&}\NormalTok{x}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{char}\NormalTok{ S}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{  n}\OperatorTok{;}
  \KeywordTok{namespace}\NormalTok{ Hash}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ MOD  }\OperatorTok{=} \DecValTok{998244353}\OperatorTok{;}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ base }\OperatorTok{=} \CharTok{\textquotesingle{}z\textquotesingle{}} \OperatorTok{+} \DecValTok{10}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ ahs}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ bhs}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ POW}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ pow}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ a}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ b}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ p}\OperatorTok{)\{} \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{b}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{b }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{*}\DecValTok{1}\BuiltInTok{LL}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ p}\OperatorTok{;}\NormalTok{ a }\OperatorTok{=} \OperatorTok{(}\NormalTok{a }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ p}\OperatorTok{;}\NormalTok{ b }\OperatorTok{\textgreater{}\textgreater{}=} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ suba}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{  ahs}\OperatorTok{[}\NormalTok{R}\OperatorTok{]} \OperatorTok{{-}} \OperatorTok{(}\NormalTok{ahs}\OperatorTok{[}\NormalTok{L }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ POW}\OperatorTok{[}\NormalTok{R }\OperatorTok{{-}}\NormalTok{ L }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)}  \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ subb}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ L}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ R}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{  bhs}\OperatorTok{[}\NormalTok{L}\OperatorTok{]} \OperatorTok{{-}} \OperatorTok{(}\NormalTok{bhs}\OperatorTok{[}\NormalTok{R }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ POW}\OperatorTok{[}\NormalTok{R }\OperatorTok{{-}}\NormalTok{ L }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)}  \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ initHash}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{}
  \NormalTok{        POW}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ x}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ POW}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ POW}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ base }\OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ x}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{            ahs}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(} \OperatorTok{(}\NormalTok{ahs}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ base}\OperatorTok{)} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \OperatorTok{\}}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ x}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textgreater{}=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i}\OperatorTok{{-}{-})\{}
  \NormalTok{            bhs}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(} \OperatorTok{(}\NormalTok{bhs}\OperatorTok{[}\NormalTok{i }\OperatorTok{+} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ base}\OperatorTok{)} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \KeywordTok{using}\NormalTok{ Hash}\OperatorTok{::}\NormalTok{initHash}\OperatorTok{;}
  \KeywordTok{using}\NormalTok{ Hash}\OperatorTok{::}\NormalTok{suba}\OperatorTok{;}
  \KeywordTok{using}\NormalTok{ Hash}\OperatorTok{::}\NormalTok{subb}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ mlen}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ qury}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
      \DataTypeTok{clock\_t}\NormalTok{ t0 }\OperatorTok{=}\NormalTok{ clock}\OperatorTok{();}
  \NormalTok{    freopen}\OperatorTok{(}\StringTok{"in.txt"}\OperatorTok{,} \StringTok{"r"}\OperatorTok{,}\NormalTok{ stdin}\OperatorTok{);}
  \NormalTok{    scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%s}\StringTok{"}\OperatorTok{,}\NormalTok{ S }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}\NormalTok{ n }\OperatorTok{=}\NormalTok{ strlen}\OperatorTok{(}\NormalTok{S }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{    initHash}\OperatorTok{(}\NormalTok{n}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{S}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{!=}\NormalTok{ S}\OperatorTok{[}\NormalTok{i }\OperatorTok{+} \DecValTok{1}\OperatorTok{])} \OperatorTok{\{}\NormalTok{ mlen}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{continue}\OperatorTok{;} \OperatorTok{\}}
          \DataTypeTok{int}\NormalTok{ L }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ R }\OperatorTok{=}\NormalTok{ i}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{while}\OperatorTok{(}\NormalTok{L }\OperatorTok{\textless{}}\NormalTok{ R}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=}\NormalTok{ L }\OperatorTok{+} \OperatorTok{((}\NormalTok{R }\OperatorTok{{-}}\NormalTok{ L }\OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{);}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{suba}\OperatorTok{(}\NormalTok{i }\OperatorTok{{-}}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ i}\OperatorTok{)} \OperatorTok{==}\NormalTok{ subb}\OperatorTok{(}\NormalTok{i }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ i }\OperatorTok{+}\NormalTok{ mid}\OperatorTok{))}\NormalTok{ ans }\OperatorTok{=}\NormalTok{ mid}\OperatorTok{,}\NormalTok{ L }\OperatorTok{=}\NormalTok{ mid}\OperatorTok{;}
              \ControlFlowTok{else}\NormalTok{ R }\OperatorTok{=}\NormalTok{ mid }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{;}
          \OperatorTok{\}}
  \NormalTok{        mlen}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ans}\OperatorTok{;}
      \OperatorTok{\}}
  
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ qury}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ i }\OperatorTok{{-}}\NormalTok{ mlen}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=}\NormalTok{ i }\OperatorTok{+} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ i }\OperatorTok{+}\NormalTok{ mlen}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}\NormalTok{j}\OperatorTok{++)}\NormalTok{ ans }\OperatorTok{+=} \OperatorTok{(}\NormalTok{j }\OperatorTok{{-}}\NormalTok{ mlen}\OperatorTok{[}\NormalTok{j}\OperatorTok{]} \OperatorTok{\textless{}=}\NormalTok{ i}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstdio\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cstring\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}cmath\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}stack\textgreater{}}
  \PreprocessorTok{\#include }\ImportTok{\textless{}iostream\textgreater{}}
  \PreprocessorTok{\#define MOD }\DecValTok{1000000007}
  \KeywordTok{using} \KeywordTok{namespace}\NormalTok{ std}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ read}\OperatorTok{()\{} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{;}\NormalTok{ scanf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,} \OperatorTok{\&}\NormalTok{x}\OperatorTok{);} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;} \OperatorTok{\}}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_ }\OperatorTok{=} \FloatTok{1e5} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ MAXD }\OperatorTok{=} \FloatTok{1e3} \OperatorTok{+} \DecValTok{100}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ head}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \KeywordTok{struct}\NormalTok{ edges}\OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ node}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ nxt}\OperatorTok{;}
  \OperatorTok{\}}\NormalTok{edge}\OperatorTok{[}\NormalTok{\_ }\OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ add}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ u}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ v}\OperatorTok{)\{}
  \NormalTok{    tot}\OperatorTok{++;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{node }\OperatorTok{=}\NormalTok{ v}\OperatorTok{;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{nxt  }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{u}\OperatorTok{];}
  \NormalTok{    head}\OperatorTok{[}\NormalTok{u}\OperatorTok{]}        \OperatorTok{=}\NormalTok{ tot}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ rt }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ C}\OperatorTok{[}\NormalTok{MAXD }\OperatorTok{+} \DecValTok{100}\OperatorTok{][}\NormalTok{MAXD }\OperatorTok{+} \DecValTok{100}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ frc}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ pow}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ a}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ b}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ P}\OperatorTok{)}  \OperatorTok{\{} \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{b}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{b }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ P}\OperatorTok{;}\NormalTok{ a }\OperatorTok{=} \OperatorTok{(}\NormalTok{a }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ P}\OperatorTok{;}\NormalTok{ b }\OperatorTok{\textgreater{}\textgreater{}=} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ inv}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{} \ControlFlowTok{return}\NormalTok{ pow}\OperatorTok{(}\NormalTok{x}\OperatorTok{,}\NormalTok{ MOD }\OperatorTok{{-}} \DecValTok{2}\OperatorTok{,}\NormalTok{ MOD}\OperatorTok{);} \OperatorTok{\}}
  \AttributeTok{const} \DataTypeTok{int}\NormalTok{ DB }\OperatorTok{=} \DecValTok{20}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ init}\OperatorTok{()\{}
  \NormalTok{    C}\OperatorTok{[}\DecValTok{0}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ MAXD}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        C}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ i}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)\{}
  \NormalTok{            C}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{j}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{ C}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{][}\NormalTok{j}\OperatorTok{]} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ C}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{][}\NormalTok{j }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
  \NormalTok{    frc}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ \_ }\OperatorTok{{-}} \DecValTok{10}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ frc}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{ frc}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*} \OperatorTok{(}\NormalTok{i}\OperatorTok{)} \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ MAXD}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ d }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ d }\OperatorTok{\textless{}=}\NormalTok{ i}\OperatorTok{;}\NormalTok{ d}\OperatorTok{++)\{}
  \NormalTok{            dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+} \OperatorTok{(}
                  \OperatorTok{(}  \OperatorTok{(} \OperatorTok{(}\NormalTok{C}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{][}\NormalTok{d }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ C}\OperatorTok{[}\NormalTok{i}\OperatorTok{][}\NormalTok{d}\OperatorTok{])} \OperatorTok{\%}\NormalTok{ MOD }\OperatorTok{)} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ frc}\OperatorTok{[}\NormalTok{i }\OperatorTok{{-}}\NormalTok{ d}\OperatorTok{]}  \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}
                      \OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ MAXD}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ inv}\OperatorTok{(}\NormalTok{frc}\OperatorTok{[}\NormalTok{i}\OperatorTok{]))} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \KeywordTok{struct}\NormalTok{ Stack}\OperatorTok{\{} \DataTypeTok{int}\NormalTok{ v}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];} \DataTypeTok{int}\NormalTok{ top}\OperatorTok{;}\NormalTok{ Stack}\OperatorTok{()\{}\NormalTok{ top }\OperatorTok{=} \DecValTok{0}\OperatorTok{;} \OperatorTok{\}} \KeywordTok{inline} \DataTypeTok{int} \OperatorTok{*}\NormalTok{GetHead}\OperatorTok{()\{} \ControlFlowTok{return} \OperatorTok{\&}\NormalTok{v}\OperatorTok{[}\DecValTok{0}\OperatorTok{];} \OperatorTok{\}} \KeywordTok{inline} \DataTypeTok{int}\OperatorTok{*}\NormalTok{ GetTail}\OperatorTok{()\{} \ControlFlowTok{return} \OperatorTok{\&}\NormalTok{v}\OperatorTok{[}\NormalTok{top}\OperatorTok{];} \OperatorTok{\}} \DataTypeTok{void}\NormalTok{ push}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{}\NormalTok{v}\OperatorTok{[}\NormalTok{top}\OperatorTok{++]} \OperatorTok{=}\NormalTok{ x}\OperatorTok{;\}} \DataTypeTok{void}\NormalTok{ pop}\OperatorTok{()\{}\NormalTok{top }\OperatorTok{{-}{-};\}} \OperatorTok{\};}
  \NormalTok{Stack S}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ val}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ NodeVal}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ dfs0}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dep}\OperatorTok{)\{}
  \NormalTok{    S}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ now }\OperatorTok{=}\NormalTok{ dep}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{*}\NormalTok{i }\OperatorTok{=}\NormalTok{ S}\OperatorTok{.}\NormalTok{GetHead}\OperatorTok{();}\NormalTok{ i }\OperatorTok{!=}\NormalTok{ S}\OperatorTok{.}\NormalTok{GetTail}\OperatorTok{();}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \OperatorTok{(}\NormalTok{  val}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+} \OperatorTok{(}\NormalTok{dp}\OperatorTok{[}\NormalTok{now}\OperatorTok{]} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ NodeVal}\OperatorTok{[*}\NormalTok{i}\OperatorTok{])} \OperatorTok{\%}\NormalTok{ MOD  }\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
  \NormalTok{        now }\OperatorTok{{-}{-};}
      \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{o}\OperatorTok{];}\NormalTok{ i }\OperatorTok{;}\NormalTok{ i }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{nxt}\OperatorTok{)\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ fa}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs0}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{,}\NormalTok{ dep }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    S}\OperatorTok{.}\NormalTok{pop}\OperatorTok{();}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    init}\OperatorTok{();}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{} \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}\NormalTok{ add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}\NormalTok{ add}\OperatorTok{(}\NormalTok{v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{);} \OperatorTok{\}}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ NodeVal}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    dfs0}\OperatorTok{(}\DecValTok{1}\OperatorTok{,} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{,} \DecValTok{1}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ NodeVal}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{+}\DecValTok{0}\BuiltInTok{ll}\OperatorTok{+}\NormalTok{ val}\OperatorTok{[}\NormalTok{i}\OperatorTok{])} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,} \OperatorTok{(}\NormalTok{ans }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ frc}\OperatorTok{[}\NormalTok{n}\OperatorTok{])} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 135.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [2] [3] [4] [5] [6] [7] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (7 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../fancyvrb.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 135.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [2] [3] [4] [5] [6] [7] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (7 pages).
  Transcript written on .../input.log.