「学习总结」久月

📅 Last Updated: 2020-09-06

📊 Word Count: 252

⏱️ Estimated Reading Time: 2 minutes

📄 PDF 📝 Source

久月也是个可爱的月份呢 QAQ~

点分治

点分治三连： - Grt( o ): 找到结点 o 所在子树的。 - solve( o ): 在以结点 o 为根的子树中，处理经过的。 - divide( o ): 点分治主函数，调用 solve(o) 处理以 o 为根经过点 o 的信息，然后删除点 o ，递归处理其儿子（divide(ex)）

注意

应保证 solve(o) 在执行过程中严格 $O(\text{size}_o)$ 否则会导致总时间复杂度不正确。
应保证两次执行 Grt() 第二次调用只是为了确定以重心为根节点的子树大小。
solve(o)中往往是在考虑所有之前访问过的子树结点到当前刚刚访问的结点之间统计答案。

例题 1

给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。

int sum;
int si[_N];
bool vis[_N];
bool judge[int(1e7 + 100)];
int qer[_N];
int MX[_N];
int ans[int(1e7 + 100)];
int rt;

void grt(int o, int f)
{
    si[o] = 1;
    MX[o] = 0;
    int MAX = 0;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (ex == f || vis[ex])
            continue;
        grt(ex, o);
        si[o] += si[ex];
        MAX = max(si[ex], MAX);
    }
    MAX = max(MAX, sum - si[o]);
    MX[o] = MAX;
    if (MAX < MX[rt])
        rt = o;
}

int cnt = 0;
int tmp[_N];
void GetAllDis(int o, int f, int dis)
{
    if (dis > 1e7)
        return;
    tmp[++cnt] = dis;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (ex == f || vis[ex])
            continue;
        GetAllDis(ex, o, dis + edge[i].w);
    }
}

queue<int> Q;
void solve(int o)
{
    judge[0] = true;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;
        cnt = 0;
        GetAllDis(ex, 0, edge[i].w);
        for (int j = 1; j <= cnt; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                if (qer[k] >= tmp[j])
                    ans[k] |= judge[qer[k] - tmp[j]];
            }
        }
        for (int j = 1; j <= cnt; j++)
        {
            judge[tmp[j]] = 1;
            Q.push(tmp[j]);
        }
    }
    while (!Q.empty())
    {
        judge[Q.front()] = 0;
        Q.pop();
    }
}

void divide(int o)
{
    vis[o] = 1;
    solve(o);
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;
        sum = si[ex];
        MX[rt = 0] = INT_MAX;
        grt(ex, 0);
        grt(rt, 0);
        divide(rt);
    }
}
int main()
{
    n = read(), m = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 1; i <= m; i++)
        qer[i] = read();
    sum = n;
    MX[rt = 0] = INT_MAX;
    grt(1, 0);
    grt(rt, 0);
    divide(rt);
    for (int i = 1; i <= m; i++)
    {
        if (ans[i])
            puts("AYE");
        else
            puts("NAY");
    }
    return 0;
}

例题 2

「luogu-P2634」「国家集训队」聪聪可可

给出一个带权树，求出所有满足长度为 $3$ 的倍数的简单路径数量。

统计时，统计每个子树内，分别统计根到子树中结点的路径长度 $\text{mod}\ 3$ 后，不同值的数量。在根节点拼接即可。

int n;
bool vis[_N];
namespace GetCenter
{
    int sum;
    int si[_N];
    int MX[_N];
    int rt;
    void dfs(int o, int f)
    {
        si[o] = 1;
        MX[o] = 0;
        int MAX = 0;
        for (int i = head[o]; i; i = edge[i].nxt)
        {
            int ex = edge[i].node;
            if (ex == f || vis[ex])
                continue;
            dfs(ex, o);
            si[o] += si[ex];
            MAX = max(MAX, si[ex]);
        }
        MAX = max(MAX, sum - si[o]);
        MX[o] = MAX;
        if (MX[rt] > MX[o])
            rt = o;
    }
    int grt(int o, int _sum)
    {
        MX[rt = 0] = INT_MAX;
        sum = _sum;
        dfs(o, 0);
        dfs(rt, 0);
        return rt;
    }
} // namespace GetCenter
using GetCenter::grt;
using GetCenter::si;

int ans = 0;
int cnt[3];
void GetDis(int o, int f, int dis)
{
    cnt[dis % 3]++;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (ex == f || vis[ex])
            continue;
        GetDis(ex, o, dis + edge[i].w);
    }
}
int Bef[3];
void solve(int o)
{
    Bef[0] = 1;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;
        memset(cnt, 0, sizeof(cnt));
        GetDis(ex, 0, edge[i].w);
        for (int i = 0; i < 3; i++)
            ans += Bef[i] * cnt[(3 - i) % 3] * 2;

        for (int i = 0; i < 3; i++)
            Bef[i] += cnt[i];
    }
    memset(Bef, 0, sizeof(Bef));
}

void divide(int o)
{
    vis[o] = true;
    solve(o);
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;
        int rt = grt(ex, si[ex]);
        divide(rt);
    }
}
int main()
{
    n = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    int rt = grt(1, n);
    divide(rt);
    ans += n;
    int A = ans, B = n * n;
    int g = gcd(A, B);
    printf("%d/%d\n", A / g, B / g);
    return 0;
}

栗题 3

「luogu-P4178」聪聪可可

给定一棵 $n$ 个节点的树，每条边有边权，求出树上两点距离小于等于 $k$ 的点对数量

对每个儿子统计所有可能的长度，乘法原理以此匹配即可。

int vis[_N];
namespace GetCenter
{
    int si[_N];
    int MX[_N];
    int rt;
    int sum;
    void dfs(int o, int f)
    {
        si[o] = 1;
        int MAX = INT_MIN;
        for (int i = head[o]; i; i = edge[i].nxt)
        {
            int ex = edge[i].node;
            if (ex == f || vis[ex])
                continue;
            dfs(ex, o);
            si[o] += si[ex];
            MAX = max(si[ex], MAX);
        }
        MAX = max(MAX, sum - si[o]);
        MX[o] = MAX;
        if (MAX < MX[rt])
            rt = o;
    }
    int grt(int o, int _sum)
    {
        MX[rt = 0] = INT_MAX;
        sum = _sum;
        dfs(o, 0);
        dfs(rt, 0);
        return rt;
    }
} // namespace GetCenter
using GetCenter::grt;
using GetCenter::si;

int judge[_N], tjt = 0;
int tmp[_N], ttt = 0;
void GetDis(int o, int f, int w)
{
    if (w > k)
        return;
    tmp[++ttt] = w;
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (ex == f || vis[ex])
            continue;
        GetDis(ex, o, w + edge[i].w);
    }
}
int ans = 0;
void solve(int o)
{
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;

        ttt = 0;
        GetDis(ex, 0, edge[i].w);

        for (int i = 1; i <= ttt; i++)
        {
            int now = k - tmp[i];
            int Q = (upper_bound(judge + 1, judge + 1 + tjt, now) - judge - 1);
            ans += Q;
        }
        for (int i = 1; i <= ttt; i++)
            judge[++tjt] = tmp[i];
        sort(judge + 1, judge + 1 + tjt);
    }
    ans += (upper_bound(judge + 1, judge + 1 + tjt, k) - judge - 1);
    tjt = 0;
}

void divide(int o)
{
    vis[o] = true;
    solve(o);
    for (int i = head[o]; i; i = edge[i].nxt)
    {
        int ex = edge[i].node;
        if (vis[ex])
            continue;
        int rt = grt(ex, si[ex]);
        divide(rt);
    }
}

int main()
{
    n = read();
    for (int i = 1; i <= n - 1; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, w);
    }
    k = read();
    int rt = grt(1, n);
    divide(rt);
    printf("%d", ans);
    return 0;
}

线段树合并

栗题

「luogu-P4556」「Vani有约会」雨天的尾巴

首先村落里的一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$ 次发放，每次选择两个房屋 $(x , y)$ ，然后对于 $x$ 到 $y$ 的路径上(含 $x$ 和 $y$ )每座房子里发放一袋 $z$ 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

重点是维护树上差分，然后在每一个叶子结点，建立一棵线段树，到达每一个非叶子结点，合并其子节点的线段树。

线段树应动态开点，保证空间复杂度正确。

marge

分情况讨论：

int marge(int x, int y, int nowl, int nowr){
    if(!x) return y;
    if(!y) return x;
    if(nowl == nowr) return (Val[x].Max += Val[y].Max, x);
    int mid = (nowl + nowr) >> 1;
    ls(x) = marge(ls(x), ls(y), nowl, mid);
    rs(x) = marge(rs(x), rs(y), mid + 1, nowr);
    maintain(x);
    return x;
}

📚 Version History

Source Code Change History

v1 📅 2020-09-06 20:05:35

🔗 Source Hash: 4ca42a88e3466fb6413779bc4855e23ae4fae06c6b18cebca98f02b9acdb701a

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_「学习总结」久月.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」久月.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.../2b821c7b61.pdf.md', '-o', 'cache/2b821c7b61.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] [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={「学习总结」久月},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」久月}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-09-06 20:05:35}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  久月也是个可爱的月份呢 QAQ\textasciitilde{}
  
  \subsection{点分治}\label{ux70b9ux5206ux6cbb}
  
  点分治三连： - Grt( o ): 找到结点 o 所在子树的 。 - solve( o ): 在以结点
  o 为根的子树中，处理经过 的 。 - divide( o ): 点分治主函数，调用
  \texttt{solve(o)} 处理以 o 为根 经过点 o 的信息，然后删除点 o
  ，递归处理其儿子（\texttt{divide(ex)}）
  
  \paragraph{注意}\label{ux6ce8ux610f}
  
  \begin{itemize}
  \tightlist
  \item
    应保证 \texttt{solve(o)} 在执行过程中严格 \(O(\text{size}_o)\)
    否则会导致总时间复杂度不正确。
  \item
    应保证 两次执行 \texttt{Grt()}
    第二次调用只是为了确定以重心为根节点的子树大小。
  \item
    \texttt{solve(o)}中往往是在考虑所有之前访问过的子树结点 到
    当前刚刚访问的结点 之间统计答案。
  \end{itemize}
  
  \subsubsection{例题 1}\label{ux4f8bux9898-1}
  
  给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ sum}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{bool}\NormalTok{ vis}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{bool}\NormalTok{ judge}\OperatorTok{[}\DataTypeTok{int}\OperatorTok{(}\FloatTok{1e7} \OperatorTok{+} \DecValTok{100}\OperatorTok{)];}
  \DataTypeTok{int}\NormalTok{ qer}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ MX}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ ans}\OperatorTok{[}\DataTypeTok{int}\OperatorTok{(}\FloatTok{1e7} \OperatorTok{+} \DecValTok{100}\OperatorTok{)];}
  \DataTypeTok{int}\NormalTok{ rt}\OperatorTok{;}
  
  \DataTypeTok{void}\NormalTok{ grt}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ MAX }\OperatorTok{=} \DecValTok{0}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        grt}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{);}
  \NormalTok{        si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{];}
  \NormalTok{        MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{],}\NormalTok{ MAX}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MAX}\OperatorTok{,}\NormalTok{ sum }\OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
  \NormalTok{    MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX}\OperatorTok{;}
      \ControlFlowTok{if} \OperatorTok{(}\NormalTok{MAX }\OperatorTok{\textless{}}\NormalTok{ MX}\OperatorTok{[}\NormalTok{rt}\OperatorTok{])}
  \NormalTok{        rt }\OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ cnt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ GetAllDis}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dis}\OperatorTok{)}
  \OperatorTok{\{}
      \ControlFlowTok{if} \OperatorTok{(}\NormalTok{dis }\OperatorTok{\textgreater{}} \FloatTok{1e7}\OperatorTok{)}
          \ControlFlowTok{return}\OperatorTok{;}
  \NormalTok{    tmp}\OperatorTok{[++}\NormalTok{cnt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ dis}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        GetAllDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{,}\NormalTok{ dis }\OperatorTok{+}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  
  \NormalTok{queue}\OperatorTok{\textless{}}\DataTypeTok{int}\OperatorTok{\textgreater{}}\NormalTok{ Q}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ solve}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    judge}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        cnt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{        GetAllDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ cnt}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)}
          \OperatorTok{\{}
              \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ k }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ k }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ k}\OperatorTok{++)}
              \OperatorTok{\{}
                  \ControlFlowTok{if} \OperatorTok{(}\NormalTok{qer}\OperatorTok{[}\NormalTok{k}\OperatorTok{]} \OperatorTok{\textgreater{}=}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{j}\OperatorTok{])}
  \NormalTok{                    ans}\OperatorTok{[}\NormalTok{k}\OperatorTok{]} \OperatorTok{|=}\NormalTok{ judge}\OperatorTok{[}\NormalTok{qer}\OperatorTok{[}\NormalTok{k}\OperatorTok{]} \OperatorTok{{-}}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{j}\OperatorTok{]];}
              \OperatorTok{\}}
          \OperatorTok{\}}
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ j }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ j }\OperatorTok{\textless{}=}\NormalTok{ cnt}\OperatorTok{;}\NormalTok{ j}\OperatorTok{++)}
          \OperatorTok{\{}
  \NormalTok{            judge}\OperatorTok{[}\NormalTok{tmp}\OperatorTok{[}\NormalTok{j}\OperatorTok{]]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{            Q}\OperatorTok{.}\NormalTok{push}\OperatorTok{(}\NormalTok{tmp}\OperatorTok{[}\NormalTok{j}\OperatorTok{]);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \ControlFlowTok{while} \OperatorTok{(!}\NormalTok{Q}\OperatorTok{.}\NormalTok{empty}\OperatorTok{())}
      \OperatorTok{\{}
  \NormalTok{        judge}\OperatorTok{[}\NormalTok{Q}\OperatorTok{.}\NormalTok{front}\OperatorTok{()]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{        Q}\OperatorTok{.}\NormalTok{pop}\OperatorTok{();}
      \OperatorTok{\}}
  \OperatorTok{\}}
  
  \DataTypeTok{void}\NormalTok{ divide}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    vis}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    solve}\OperatorTok{(}\NormalTok{o}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        sum }\OperatorTok{=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{];}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{;}
  \NormalTok{        grt}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{        grt}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{        divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()}
  \OperatorTok{\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ w }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
      \OperatorTok{\}}
      \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
  \NormalTok{        qer}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    sum }\OperatorTok{=}\NormalTok{ n}\OperatorTok{;}
  \NormalTok{    MX}\OperatorTok{[}\NormalTok{rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{;}
  \NormalTok{    grt}\OperatorTok{(}\DecValTok{1}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{    grt}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{    divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ m}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
      \OperatorTok{\{}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ans}\OperatorTok{[}\NormalTok{i}\OperatorTok{])}
  \NormalTok{            puts}\OperatorTok{(}\StringTok{"AYE"}\OperatorTok{);}
          \ControlFlowTok{else}
  \NormalTok{            puts}\OperatorTok{(}\StringTok{"NAY"}\OperatorTok{);}
      \OperatorTok{\}}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \subsubsection{例题 2}\label{ux4f8bux9898-2}
  
  \paragraph{「luogu-P2634」「国家集训队」聪聪可可}\label{luogu-p2634ux56fdux5bb6ux96c6ux8badux961fux806aux806aux53efux53ef}
  
  给出一个带权树，求出所有满足长度为 \(3\) 的倍数的简单路径数量。
  
  统计时，统计每个子树内，分别统计 根到子树中结点的路径长度
  \(\text{mod}\ 3\) 后，不同值的数量。 在根节点拼接即可。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{;}
  \DataTypeTok{bool}\NormalTok{ vis}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \KeywordTok{namespace}\NormalTok{ GetCenter}
  \OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ sum}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ MX}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ rt}\OperatorTok{;}
      \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{)}
      \OperatorTok{\{}
  \NormalTok{        si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ MAX }\OperatorTok{=} \DecValTok{0}\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{)}
          \OperatorTok{\{}
              \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
                  \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            dfs}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{);}
  \NormalTok{            si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{];}
  \NormalTok{            MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MAX}\OperatorTok{,}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{]);}
          \OperatorTok{\}}
  \NormalTok{        MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MAX}\OperatorTok{,}\NormalTok{ sum }\OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{MX}\OperatorTok{[}\NormalTok{rt}\OperatorTok{]} \OperatorTok{\textgreater{}}\NormalTok{ MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{])}
  \NormalTok{            rt }\OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ grt}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ \_sum}\OperatorTok{)}
      \OperatorTok{\{}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{;}
  \NormalTok{        sum }\OperatorTok{=}\NormalTok{ \_sum}\OperatorTok{;}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{o}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ rt}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}} \CommentTok{// namespace GetCenter}
  \KeywordTok{using}\NormalTok{ GetCenter}\OperatorTok{::}\NormalTok{grt}\OperatorTok{;}
  \KeywordTok{using}\NormalTok{ GetCenter}\OperatorTok{::}\NormalTok{si}\OperatorTok{;}
  
  \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ cnt}\OperatorTok{[}\DecValTok{3}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ GetDis}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dis}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    cnt}\OperatorTok{[}\NormalTok{dis }\OperatorTok{\%} \DecValTok{3}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        GetDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{,}\NormalTok{ dis }\OperatorTok{+}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ Bef}\OperatorTok{[}\DecValTok{3}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ solve}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    Bef}\OperatorTok{[}\DecValTok{0}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        memset}\OperatorTok{(}\NormalTok{cnt}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{cnt}\OperatorTok{));}
  \NormalTok{        GetDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}} \DecValTok{3}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
  \NormalTok{            ans }\OperatorTok{+=}\NormalTok{ Bef}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{*}\NormalTok{ cnt}\OperatorTok{[(}\DecValTok{3} \OperatorTok{{-}}\NormalTok{ i}\OperatorTok{)} \OperatorTok{\%} \DecValTok{3}\OperatorTok{]} \OperatorTok{*} \DecValTok{2}\OperatorTok{;}
  
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}} \DecValTok{3}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
  \NormalTok{            Bef}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ cnt}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
      \OperatorTok{\}}
  \NormalTok{    memset}\OperatorTok{(}\NormalTok{Bef}\OperatorTok{,} \DecValTok{0}\OperatorTok{,} \KeywordTok{sizeof}\OperatorTok{(}\NormalTok{Bef}\OperatorTok{));}
  \OperatorTok{\}}
  
  \DataTypeTok{void}\NormalTok{ divide}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    vis}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\OperatorTok{;}
  \NormalTok{    solve}\OperatorTok{(}\NormalTok{o}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ grt}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{]);}
  \NormalTok{        divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()}
  \OperatorTok{\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ w }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ grt}\OperatorTok{(}\DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{);}
  \NormalTok{    divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
  \NormalTok{    ans }\OperatorTok{+=}\NormalTok{ n}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ A }\OperatorTok{=}\NormalTok{ ans}\OperatorTok{,}\NormalTok{ B }\OperatorTok{=}\NormalTok{ n }\OperatorTok{*}\NormalTok{ n}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ g }\OperatorTok{=}\NormalTok{ gcd}\OperatorTok{(}\NormalTok{A}\OperatorTok{,}\NormalTok{ B}\OperatorTok{);}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{/}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ A }\OperatorTok{/}\NormalTok{ g}\OperatorTok{,}\NormalTok{ B }\OperatorTok{/}\NormalTok{ g}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \paragraph{栗题 3}\label{ux6817ux9898-3}
  
  \paragraph{「luogu-P4178」聪聪可可}\label{luogu-p4178ux806aux806aux53efux53ef}
  
  给定一棵 \(n\) 个节点的树，每条边有边权，求出树上两点距离小于等于 \(k\)
  的点对数量
  
  对每个儿子统计所有可能的长度，乘法原理以此匹配即可。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ vis}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
  \KeywordTok{namespace}\NormalTok{ GetCenter}
  \OperatorTok{\{}
      \DataTypeTok{int}\NormalTok{ si}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ MX}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ rt}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ sum}\OperatorTok{;}
      \DataTypeTok{void}\NormalTok{ dfs}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{)}
      \OperatorTok{\{}
  \NormalTok{        si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{1}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ MAX }\OperatorTok{=}\NormalTok{ INT\_MIN}\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{)}
          \OperatorTok{\{}
              \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
              \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
                  \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{            dfs}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{);}
  \NormalTok{            si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{];}
  \NormalTok{            MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{],}\NormalTok{ MAX}\OperatorTok{);}
          \OperatorTok{\}}
  \NormalTok{        MAX }\OperatorTok{=}\NormalTok{ max}\OperatorTok{(}\NormalTok{MAX}\OperatorTok{,}\NormalTok{ sum }\OperatorTok{{-}}\NormalTok{ si}\OperatorTok{[}\NormalTok{o}\OperatorTok{]);}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ MAX}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{MAX }\OperatorTok{\textless{}}\NormalTok{ MX}\OperatorTok{[}\NormalTok{rt}\OperatorTok{])}
  \NormalTok{            rt }\OperatorTok{=}\NormalTok{ o}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{int}\NormalTok{ grt}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ \_sum}\OperatorTok{)}
      \OperatorTok{\{}
  \NormalTok{        MX}\OperatorTok{[}\NormalTok{rt }\OperatorTok{=} \DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ INT\_MAX}\OperatorTok{;}
  \NormalTok{        sum }\OperatorTok{=}\NormalTok{ \_sum}\OperatorTok{;}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{o}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
  \NormalTok{        dfs}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \DecValTok{0}\OperatorTok{);}
          \ControlFlowTok{return}\NormalTok{ rt}\OperatorTok{;}
      \OperatorTok{\}}
  \OperatorTok{\}} \CommentTok{// namespace GetCenter}
  \KeywordTok{using}\NormalTok{ GetCenter}\OperatorTok{::}\NormalTok{grt}\OperatorTok{;}
  \KeywordTok{using}\NormalTok{ GetCenter}\OperatorTok{::}\NormalTok{si}\OperatorTok{;}
  
  \DataTypeTok{int}\NormalTok{ judge}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{],}\NormalTok{ tjt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{\_N}\OperatorTok{],}\NormalTok{ ttt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ GetDis}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ w}\OperatorTok{)}
  \OperatorTok{\{}
      \ControlFlowTok{if} \OperatorTok{(}\NormalTok{w }\OperatorTok{\textgreater{}}\NormalTok{ k}\OperatorTok{)}
          \ControlFlowTok{return}\OperatorTok{;}
  \NormalTok{    tmp}\OperatorTok{[++}\NormalTok{ttt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ w}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{ex }\OperatorTok{==}\NormalTok{ f }\OperatorTok{||}\NormalTok{ vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        GetDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ o}\OperatorTok{,}\NormalTok{ w }\OperatorTok{+}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \DataTypeTok{void}\NormalTok{ solve}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
  
  \NormalTok{        ttt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{        GetDis}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,} \DecValTok{0}\OperatorTok{,}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{w}\OperatorTok{);}
  
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ ttt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
          \OperatorTok{\{}
              \DataTypeTok{int}\NormalTok{ now }\OperatorTok{=}\NormalTok{ k }\OperatorTok{{-}}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
              \DataTypeTok{int}\NormalTok{ Q }\OperatorTok{=} \OperatorTok{(}\NormalTok{upper\_bound}\OperatorTok{(}\NormalTok{judge }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ judge }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tjt}\OperatorTok{,}\NormalTok{ now}\OperatorTok{)} \OperatorTok{{-}}\NormalTok{ judge }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
  \NormalTok{            ans }\OperatorTok{+=}\NormalTok{ Q}\OperatorTok{;}
          \OperatorTok{\}}
          \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ ttt}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
  \NormalTok{            judge}\OperatorTok{[++}\NormalTok{tjt}\OperatorTok{]} \OperatorTok{=}\NormalTok{ tmp}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
  \NormalTok{        sort}\OperatorTok{(}\NormalTok{judge }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ judge }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tjt}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    ans }\OperatorTok{+=} \OperatorTok{(}\NormalTok{upper\_bound}\OperatorTok{(}\NormalTok{judge }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ judge }\OperatorTok{+} \DecValTok{1} \OperatorTok{+}\NormalTok{ tjt}\OperatorTok{,}\NormalTok{ k}\OperatorTok{)} \OperatorTok{{-}}\NormalTok{ judge }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{);}
  \NormalTok{    tjt }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  
  \DataTypeTok{void}\NormalTok{ divide}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)}
  \OperatorTok{\{}
  \NormalTok{    vis}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \KeywordTok{true}\OperatorTok{;}
  \NormalTok{    solve}\OperatorTok{(}\NormalTok{o}\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{)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ ex }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if} \OperatorTok{(}\NormalTok{vis}\OperatorTok{[}\NormalTok{ex}\OperatorTok{])}
              \ControlFlowTok{continue}\OperatorTok{;}
          \DataTypeTok{int}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ grt}\OperatorTok{(}\NormalTok{ex}\OperatorTok{,}\NormalTok{ si}\OperatorTok{[}\NormalTok{ex}\OperatorTok{]);}
  \NormalTok{        divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()}
  \OperatorTok{\{}
  \NormalTok{    n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \ControlFlowTok{for} \OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)}
      \OperatorTok{\{}
          \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ w }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{,}\NormalTok{ w}\OperatorTok{);}
      \OperatorTok{\}}
  \NormalTok{    k }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
      \DataTypeTok{int}\NormalTok{ rt }\OperatorTok{=}\NormalTok{ grt}\OperatorTok{(}\DecValTok{1}\OperatorTok{,}\NormalTok{ n}\OperatorTok{);}
  \NormalTok{    divide}\OperatorTok{(}\NormalTok{rt}\OperatorTok{);}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d}\StringTok{"}\OperatorTok{,}\NormalTok{ ans}\OperatorTok{);}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \subsection{线段树合并}\label{ux7ebfux6bb5ux6811ux5408ux5e76}
  
  \subsubsection{栗题}\label{ux6817ux9898}
  
  \paragraph{「luogu-P4556」「Vani有约会」雨天的尾巴}\label{luogu-p4556vaniux6709ux7ea6ux4f1aux96e8ux5929ux7684ux5c3eux5df4}
  
  首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\)
  次发放，每次选择两个房屋 \((x , y)\)，然后对于 \(x\) 到 \(y\)
  的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。
  
  然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
  
  重点是维护树上差分，然后在每一个叶子结点，建立一棵线段树，到达每一个非叶子结点，合并其子节点的线段树。
  
  线段树应动态开点，保证空间复杂度正确。
  
  \paragraph{marge}\label{marge}
  
  分情况讨论：
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{int}\NormalTok{ marge}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ y}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowl}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ nowr}\OperatorTok{)\{}
      \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{x}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ y}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{y}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ x}\OperatorTok{;}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{nowl }\OperatorTok{==}\NormalTok{ nowr}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{Val}\OperatorTok{[}\NormalTok{x}\OperatorTok{].}\NormalTok{Max }\OperatorTok{+=}\NormalTok{ Val}\OperatorTok{[}\NormalTok{y}\OperatorTok{].}\NormalTok{Max}\OperatorTok{,}\NormalTok{ x}\OperatorTok{);}
      \DataTypeTok{int}\NormalTok{ mid }\OperatorTok{=} \OperatorTok{(}\NormalTok{nowl }\OperatorTok{+}\NormalTok{ nowr}\OperatorTok{)} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{;}
  \NormalTok{    ls}\OperatorTok{(}\NormalTok{x}\OperatorTok{)} \OperatorTok{=}\NormalTok{ marge}\OperatorTok{(}\NormalTok{ls}\OperatorTok{(}\NormalTok{x}\OperatorTok{),}\NormalTok{ ls}\OperatorTok{(}\NormalTok{y}\OperatorTok{),}\NormalTok{ nowl}\OperatorTok{,}\NormalTok{ mid}\OperatorTok{);}
  \NormalTok{    rs}\OperatorTok{(}\NormalTok{x}\OperatorTok{)} \OperatorTok{=}\NormalTok{ marge}\OperatorTok{(}\NormalTok{rs}\OperatorTok{(}\NormalTok{x}\OperatorTok{),}\NormalTok{ rs}\OperatorTok{(}\NormalTok{y}\OperatorTok{),}\NormalTok{ mid }\OperatorTok{+} \DecValTok{1}\OperatorTok{,}\NormalTok{ nowr}\OperatorTok{);}
  \NormalTok{    maintain}\OperatorTok{(}\NormalTok{x}\OperatorTok{);}
      \ControlFlowTok{return}\NormalTok{ x}\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 116.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] [3] [4] [5] [6] [7] [8] [9] (.../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 (9 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 116.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [1] [2] [3] [4] [5] [6] [7] [8] [9] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (9 pages).
  Transcript written on .../input.log.