「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」树

📅 Last Updated: 2020-07-10

📊 Word Count: 693

⏱️ Estimated Reading Time: 5 minutes

📄 PDF 📝 Source

给定一棵 $n$ 个结点的有根树 $T$ ，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$ 。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$ ，定义 $x$ 的价值为：

$val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))$ 其中 $d(x,y)$ 。

表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数， $d(x,x) = 0$ 。 $\oplus$ 表示异或运算。

请你求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

考虑每个结点对其所有祖先的贡献。每个结点建立 trie，初始先只存这个结点的权值，然后从底向上合并每个儿子结点上的 trie，然后再全局加一，完成后统计答案。

全局加一（维护异或和）

这个不太好表述啊~
01-trie数 是指字符集为 $\{0,1\}$ 的 Trie 树。
01-trie树可以用来维护一堆数字的异或和，支持修改（删除+重新插入），和全部维护值加一。

如果要维护异或和，需要按值从低位到高位建立trie。

一个约定：文中说当前节点往上指当前节点到根这条路径，当前节点往下指当前结点的子树。

插入&删除

如果要维护异或和，我们只需要知道某一位上0和1个数的奇偶性即可，也就是对于数字1来说，当且仅当这一位上数字1的个数为奇数时，这一位上的数字才是1。

对于每一个节点，我们需要记录以下三个量： - ch[o][0/1]指节点o的两个儿子，ch[o][0]指下一位是0，同理ch[o][1]指下一位是0。 - w[o]指节点o到其父亲节点这条边上数值的数量（权值）。每插入一个数字x，x二进制拆分后在 trie树上路径的权值都会+1。 - xorv[o]指以o为根的子树维护的异或和。

具体维护结点的代码如下所示。

void maintain(int o){
        w[o] = xorv[o] = 0;
        if(ch[o][0]){ w[o] += w[ch[o][0]]; xorv[o] ^=  xorv[ch[o][0]] << 1; }
        if(ch[o][1]){ w[o] += w[ch[o][1]]; xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1); }
        //w[o] = w[o] & 1;
        //只需知道奇偶性即可，不需要具体的值。当然这句话删掉也可以，因为上文就只利用了他的奇偶性。
    }

插入和删除的代码非常相似。

需要注意的地方就是：

这里的MAXH指trie的深度，也就是强制让每一个叶子节点到根的距离为MAXH。对于一些比较小的值，可能有时候不需要建立这么深（例如：如果插入数字4，分解成二进制后为100，从根开始插入001这三位即可），但是我们强制插入MAXH位。这样做的目的是为了便于全局+1时处理进位。例如：如果原数字是3（11），++之后变成4（100），如果当初插入3时只插入了2位，那这里的进位就没了。
插入和删除，只需要修改叶子节点的w[]即可，在回溯的过程中一路维护即可。

namespace trie{
    const int MAXH = 21; 
    int ch[_ * (MAXH + 1)][2], w[_ * (MAXH + 1)], xorv[_ * (MAXH + 1)];
    int tot = 0;
    int mknode(){ ++tot; ch[tot][1] = ch[tot][0] = w[tot] = xorv[tot] = 0; return tot;}
    void maintain(int o){
        w[o] = xorv[o] = 0;
        if(ch[o][0]){ w[o] += w[ch[o][0]]; xorv[o] ^=  xorv[ch[o][0]] << 1; }
        if(ch[o][1]){ w[o] += w[ch[o][1]]; xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1); }
        w[o] = w[o] & 1;
    }
    void insert(int &o, int x, int dp){
        if(!o) o = mknode();
        if(dp > MAXH) return (void)(w[o] ++);
        insert(ch[o][ x&1 ], x >> 1, dp + 1);
        maintain(o);
    }
}

全局加一

void addall(int o){
    swap(ch[o][0], ch[o][1]);
    if(ch[o][0]) addall(ch[o][0]);
    maintain(o);
}

不知道你能不能直接看懂呢？

我们思考一下二进制意义下+1是如何操作的。

我们只需要从低位到高位开始找第一个出现的0，把它变成1，然后这个位置后面的1都变成0即可。

下面给出几个例子感受一下。（括号内的数字表示其对应的十进制数字）

1000  (10)   + 1 = 1001   (11)
10011 (19)   + 1 = 10100  (20)
11111 (31)   + 1 = 100000 (32)
10101 (21)   + 1 = 10110  (22)
100000000111111(16447) + 1 = 100000001000000(16448)

回顾一下w[o]的定义：w[o]指节点o到其父亲节点这条边上数值的数量（权值）。

有没有感觉这个定义有点怪呢？如果在父亲结点存储到两个儿子的这条边的边权也许会更接近于习惯。但是在这里，在交换左右儿子的时候，在儿子结点存储到父亲这条边的距离，显然更加方便。

Code



namespace trie{
    const int _n = _ * 25;
    int rt[_];
    int ch[_n][2];
    int w[_n]; 
    int xorv[_n];
// w[i] is in order to save the weight of edge which is connect `i` and its `parent`.
    int tot = 0;
    void maintain(int o){
        w[o] = xorv[o] = 0;
        if(ch[o][0]){ w[o] += w[ch[o][0]]; xorv[o] ^=  xorv[ch[o][0]] << 1; }
        if(ch[o][1]){ w[o] += w[ch[o][1]]; xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1); }
    }
    inline int mknode(){ ++tot; ch[tot][0] = ch[tot][1] = 0; w[tot] = 0; return tot; }
    void insert(int &o, int x, int dp){
        if(!o) o = mknode();
        if(dp > 20) return (void)(w[o] ++);
//        if(dp == 0)cerr << "New start" << endl;
//        cerr << "inserted " << (x&1) << endl;
        insert(ch[o][ x&1 ], x >> 1, dp + 1);
        maintain(o); 
//      cerr << w[o] << endl;
    }
    void erase(int o, int x, int dp){
        if(dp > 20) return (void )(w[o]--);
        erase(ch[o][ x&1 ], x >> 1, dp + 1);
        maintain(o);
    }
    void addall(int o){
        swap(ch[o][1], ch[o][0]);
        if(ch[o][0]) addall(ch[o][0]);
        maintain(o);
    }
}

int head[_];
struct edges{
    int node;
    int nxt;
}edge[_ << 1];
int tot = 0;
void add(int u, int v){
    edge[++tot].nxt = head[u];
    head[u] = tot;
    edge[tot].node = v;
}

int n, m;
int rt;
int lztar[_];
int fa[_];
void dfs0(int o, int f){
    fa[o] = f;
    for(int i = head[o];i;i = edge[i].nxt){
        int node = edge[i].node;
        if(node == f) continue;
        dfs0(node, o);
    }
}
int V[_];
inline int get(int x){ return (fa[x] == -1 ? 0 : lztar[fa[x]]) + V[x]; }
int main()
{
#ifdef LOCAL_JUDGE
//    freopen("in.in", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
//  freopen("in.in", "r", stdin);
    clock_t c1 = clock();
    
    n = read(), m = read();
    for(int i = 1;i < n;i++){
        int u = read(), v = read(); //read();
        add(u, v); add(rt = v, u);
    }
//    show(rt);
    dfs0(rt, -1);
    for(int i = 1;i <= n;i++) { V[i] = read(); if(fa[i] != -1)trie::insert(trie::rt[fa[i]], V[i], 0);  }
//    puts("OK");
    while(m--){
        int opt = read(), x = read(); //cerr << "opt = " << opt << endl;
//        if(get(x) < 0) puts("data error");
        if(opt == 1){
            lztar[x] ++; //cerr << "add lztar[ " << x << " ]" << endl;
            if(x != rt) {
                if(fa[fa[x]])trie::erase(trie::rt[fa[fa[x]]], get(fa[x]), 0);
                V[fa[x]] ++;
                if(fa[fa[x]])trie::insert(trie::rt[fa[fa[x]]], get(fa[x]), 0);
            }
            trie::addall(trie::rt[x]);
        } else if(opt == 2){
            int v = read();
            if(x != rt) trie::erase(trie::rt[fa[x]], get(x), 0);
            V[x] -= v;
            if(x != rt) trie::insert(trie::rt[fa[x]], get(x), 0);
        } else {
            int res = 0;
            res = trie::xorv[trie::rt[x]];
            res ^= get(fa[x]);
            printf("%d\n", res);
        }
    }
    std::cerr << "\n\nTime:  " << clock() - c1 << "  ms" << std::endl;
    return 0;
}

📚 Version History

Source Code Change History

v1 📅 2020-07-10 17:26:42

🔗 Source Hash: e343f27580d27e6d5244d2e56e92d709238415764dbe586af9c9b34fba6758b6

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_「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」 树.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache/oi-blog_「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」 树.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.../3d29fe1096.pdf.md', '-o', 'cache/3d29fe1096.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={「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」 树},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」 树}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-07-10 17:26:42}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  给定一棵 \(n\) 个结点的有根树 \(T\) ，结点从 \(1\) 开始编号，根结点为
  \(1\) 号结点，每个结点有一个正整数权值 \(v_i\) 。
  
  设 \(x\) 号结点的子树内（包含 \(x\) 自身）的所有结点编号为
  \(c_1,c_2,\dots,c_k\) ，定义 \(x\) 的价值为：
  
  \(val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))\)
  其中 \(d(x,y)\) 。
  
  表示树上 \(x\) 号结点与 \(y\) 号结点间唯一简单路径所包含的边数，
  \(d(x,x) = 0\) 。 \(\oplus\) 表示异或运算。
  
  请你求出 \(\sum\limits_{i=1}^n val(i)\) 的结果。
  
  考虑每个结点对其所有祖先的贡献。 每个结点建立
  trie，初始先只存这个结点的权值，然后从底向上合并每个儿子结点上的
  trie，然后再全局加一，完成后统计答案。
  
  \subsection{全局加一（维护异或和）}\label{ux5168ux5c40ux52a0ux4e00ux7ef4ux62a4ux5f02ux6216ux548c}
  
  这个不太好表述啊\textasciitilde{}\\
  \texttt{01-trie数} 是指字符集为 \(\{0,1\}\) 的 Trie 树。\\
  \texttt{01-trie树}可以用来维护一堆数字的异或和，支持修改（删除+重新插入），和全部维护值加一。
  
  如果要维护异或和，需要按值从低位到高位建立\texttt{trie}。
  
  \textbf{一个约定}：文中说当前节点\textbf{往上}指当前节点到根这条路径，当前节点\textbf{往下}指当前结点的子树。
  
  \subsubsection{插入\&删除}\label{ux63d2ux5165ux5220ux9664}
  
  如果要维护异或和，我们只需要知道某一位上\texttt{0}和\texttt{1}个数的奇偶性即可，也就是对于数字\texttt{1}来说，当且仅当这一位上数字\texttt{1}的个数为奇数时，这一位上的数字才是\texttt{1}。
  
  对于每一个节点，我们需要记录以下三个量： -
  \texttt{ch{[}o{]}{[}0/1{]}}指节点\texttt{o}的两个儿子，\texttt{ch{[}o{]}{[}0{]}}指下一位是\texttt{0}，同理\texttt{ch{[}o{]}{[}1{]}}指下一位是\texttt{0}。
  -
  \texttt{w{[}o{]}}指节点\texttt{o}到其父亲节点这条边上数值的数量（权值）。每插入一个数字\texttt{x}，\texttt{x}二进制拆分后在
  \texttt{trie}树上 路径的权值都会\texttt{+1}。 -
  \texttt{xorv{[}o{]}}指以\texttt{o}为根的子树维护的异或和。
  
  具体维护结点的代码如下所示。
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{void}\NormalTok{ maintain}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{        w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=}\NormalTok{  xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=} \OperatorTok{(}\NormalTok{xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{|} \OperatorTok{(}\NormalTok{w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\&} \DecValTok{1}\OperatorTok{);} \OperatorTok{\}}
          \CommentTok{//w[o] = w[o] \& 1;}
          \CommentTok{//只需知道奇偶性即可，不需要具体的值。当然这句话删掉也可以，因为上文就只利用了他的奇偶性。}
      \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  插入和删除的代码非常相似。
  
  需要注意的地方就是：
  
  \begin{itemize}
  \item
    这里的\texttt{MAXH}指\texttt{trie}的深度，也就是强制让每一个叶子节点到根的距离为\texttt{MAXH}。对于一些比较小的值，可能有时候不需要建立这么深（例如：如果插入数字\texttt{4}，分解成二进制后为\texttt{100}，
    从根开始插入\texttt{001}这三位即可），但是我们强制插入\texttt{MAXH}位。这样做的目的是为了便于全局\texttt{+1}时处理进位。例如：如果原数字是\texttt{3}（\texttt{11}），++之后变成\texttt{4}（\texttt{100}），如果当初插入\texttt{3}时只插入了\texttt{2}位，那这里的进位就没了。
  \item
    插入和删除，只需要修改叶子节点的\texttt{w{[}{]}}即可，在回溯的过程中一路维护即可。
  \end{itemize}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \KeywordTok{namespace}\NormalTok{ trie}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ MAXH }\OperatorTok{=} \DecValTok{21}\OperatorTok{;} 
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_ }\OperatorTok{*} \OperatorTok{(}\NormalTok{MAXH }\OperatorTok{+} \DecValTok{1}\OperatorTok{)][}\DecValTok{2}\OperatorTok{],}\NormalTok{ w}\OperatorTok{[}\NormalTok{\_ }\OperatorTok{*} \OperatorTok{(}\NormalTok{MAXH }\OperatorTok{+} \DecValTok{1}\OperatorTok{)],}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{\_ }\OperatorTok{*} \OperatorTok{(}\NormalTok{MAXH }\OperatorTok{+} \DecValTok{1}\OperatorTok{)];}
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ mknode}\OperatorTok{()\{} \OperatorTok{++}\NormalTok{tot}\OperatorTok{;}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ w}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{return}\NormalTok{ tot}\OperatorTok{;\}}
      \DataTypeTok{void}\NormalTok{ maintain}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{        w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=}\NormalTok{  xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=} \OperatorTok{(}\NormalTok{xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{|} \OperatorTok{(}\NormalTok{w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\&} \DecValTok{1}\OperatorTok{);} \OperatorTok{\}}
  \NormalTok{        w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\&} \DecValTok{1}\OperatorTok{;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ insert}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{\&}\NormalTok{o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ mknode}\OperatorTok{();}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dp }\OperatorTok{\textgreater{}}\NormalTok{ MAXH}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{++);}
  \NormalTok{        insert}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{ x}\OperatorTok{\&}\DecValTok{1} \OperatorTok{],}\NormalTok{ x }\OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{,}\NormalTok{ dp }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \subsubsection{全局加一}\label{ux5168ux5c40ux52a0ux4e00}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DataTypeTok{void}\NormalTok{ addall}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{    swap}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{],}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]);}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}\NormalTok{ addall}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]);}
  \NormalTok{    maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  不知道你能不能直接看懂呢？
  
  我们思考一下二进制意义下\texttt{+1}是如何操作的。
  
  我们只需要从低位到高位开始找第一个出现的\texttt{0}，把它变成\texttt{1}，然后这个位置后面的\texttt{1}都变成\texttt{0}即可。
  
  下面给出几个例子感受一下。（括号内的数字表示其对应的十进制数字）
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \DecValTok{1000}  \OperatorTok{(}\DecValTok{10}\OperatorTok{)}   \OperatorTok{+} \DecValTok{1} \OperatorTok{=} \DecValTok{1001}   \OperatorTok{(}\DecValTok{11}\OperatorTok{)}
  \DecValTok{10011} \OperatorTok{(}\DecValTok{19}\OperatorTok{)}   \OperatorTok{+} \DecValTok{1} \OperatorTok{=} \DecValTok{10100}  \OperatorTok{(}\DecValTok{20}\OperatorTok{)}
  \DecValTok{11111} \OperatorTok{(}\DecValTok{31}\OperatorTok{)}   \OperatorTok{+} \DecValTok{1} \OperatorTok{=} \DecValTok{100000} \OperatorTok{(}\DecValTok{32}\OperatorTok{)}
  \DecValTok{10101} \OperatorTok{(}\DecValTok{21}\OperatorTok{)}   \OperatorTok{+} \DecValTok{1} \OperatorTok{=} \DecValTok{10110}  \OperatorTok{(}\DecValTok{22}\OperatorTok{)}
  \DecValTok{100000000111111}\OperatorTok{(}\DecValTok{16447}\OperatorTok{)} \OperatorTok{+} \DecValTok{1} \OperatorTok{=} \DecValTok{100000001000000}\OperatorTok{(}\DecValTok{16448}\OperatorTok{)}
  \end{Highlighting}
  \end{Shaded}
  
  回顾一下\texttt{w{[}o{]}}的定义：\texttt{w{[}o{]}}指节点\texttt{o}到其父亲节点这条边上数值的数量（权值）。
  
  有没有感觉这个定义有点怪呢？如果在父亲结点存储到两个儿子的这条边的边权也许会更接近于习惯。但是在这里，在交换左右儿子的时候，在儿子结点存储到父亲这条边的距离，显然更加方便。
  
  \section{Code}\label{code}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  
  
  \KeywordTok{namespace}\NormalTok{ trie}\OperatorTok{\{}
      \AttributeTok{const} \DataTypeTok{int}\NormalTok{ \_n }\OperatorTok{=}\NormalTok{ \_ }\OperatorTok{*} \DecValTok{25}\OperatorTok{;}
      \DataTypeTok{int}\NormalTok{ rt}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ ch}\OperatorTok{[}\NormalTok{\_n}\OperatorTok{][}\DecValTok{2}\OperatorTok{];}
      \DataTypeTok{int}\NormalTok{ w}\OperatorTok{[}\NormalTok{\_n}\OperatorTok{];} 
      \DataTypeTok{int}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{\_n}\OperatorTok{];}
  \CommentTok{// w[i] is in order to save the weight of edge which is connect \textasciigrave{}i\textasciigrave{} and its \textasciigrave{}parent\textasciigrave{}.}
      \DataTypeTok{int}\NormalTok{ tot }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \DataTypeTok{void}\NormalTok{ maintain}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{        w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=}\NormalTok{  xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{])\{}\NormalTok{ w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{+=}\NormalTok{ w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]];}\NormalTok{ xorv}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{\^{}=} \OperatorTok{(}\NormalTok{xorv}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{|} \OperatorTok{(}\NormalTok{w}\OperatorTok{[}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{]]} \OperatorTok{\&} \DecValTok{1}\OperatorTok{);} \OperatorTok{\}}
      \OperatorTok{\}}
      \KeywordTok{inline} \DataTypeTok{int}\NormalTok{ mknode}\OperatorTok{()\{} \OperatorTok{++}\NormalTok{tot}\OperatorTok{;}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{0}\OperatorTok{]} \OperatorTok{=}\NormalTok{ ch}\OperatorTok{[}\NormalTok{tot}\OperatorTok{][}\DecValTok{1}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;}\NormalTok{ w}\OperatorTok{[}\NormalTok{tot}\OperatorTok{]} \OperatorTok{=} \DecValTok{0}\OperatorTok{;} \ControlFlowTok{return}\NormalTok{ tot}\OperatorTok{;} \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ insert}\OperatorTok{(}\DataTypeTok{int} \OperatorTok{\&}\NormalTok{o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(!}\NormalTok{o}\OperatorTok{)}\NormalTok{ o }\OperatorTok{=}\NormalTok{ mknode}\OperatorTok{();}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dp }\OperatorTok{\textgreater{}} \DecValTok{20}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void}\OperatorTok{)(}\NormalTok{w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{++);}
  \CommentTok{//        if(dp == 0)cerr \textless{}\textless{} "New start" \textless{}\textless{} endl;}
  \CommentTok{//        cerr \textless{}\textless{} "inserted " \textless{}\textless{} (x\&1) \textless{}\textless{} endl;}
  \NormalTok{        insert}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{ x}\OperatorTok{\&}\DecValTok{1} \OperatorTok{],}\NormalTok{ x }\OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{,}\NormalTok{ dp }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);} 
  \CommentTok{//      cerr \textless{}\textless{} w[o] \textless{}\textless{} endl;}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ erase}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ x}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ dp}\OperatorTok{)\{}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{dp }\OperatorTok{\textgreater{}} \DecValTok{20}\OperatorTok{)} \ControlFlowTok{return} \OperatorTok{(}\DataTypeTok{void} \OperatorTok{)(}\NormalTok{w}\OperatorTok{[}\NormalTok{o}\OperatorTok{]{-}{-});}
  \NormalTok{        erase}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\NormalTok{ x}\OperatorTok{\&}\DecValTok{1} \OperatorTok{],}\NormalTok{ x }\OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{,}\NormalTok{ dp }\OperatorTok{+} \DecValTok{1}\OperatorTok{);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
      \DataTypeTok{void}\NormalTok{ addall}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{)\{}
  \NormalTok{        swap}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{1}\OperatorTok{],}\NormalTok{ ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]);}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{])}\NormalTok{ addall}\OperatorTok{(}\NormalTok{ch}\OperatorTok{[}\NormalTok{o}\OperatorTok{][}\DecValTok{0}\OperatorTok{]);}
  \NormalTok{        maintain}\OperatorTok{(}\NormalTok{o}\OperatorTok{);}
      \OperatorTok{\}}
  \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{    edge}\OperatorTok{[++}\NormalTok{tot}\OperatorTok{].}\NormalTok{nxt }\OperatorTok{=}\NormalTok{ head}\OperatorTok{[}\NormalTok{u}\OperatorTok{];}
  \NormalTok{    head}\OperatorTok{[}\NormalTok{u}\OperatorTok{]} \OperatorTok{=}\NormalTok{ tot}\OperatorTok{;}
  \NormalTok{    edge}\OperatorTok{[}\NormalTok{tot}\OperatorTok{].}\NormalTok{node }\OperatorTok{=}\NormalTok{ v}\OperatorTok{;}
  \OperatorTok{\}}
  
  \DataTypeTok{int}\NormalTok{ n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ rt}\OperatorTok{;}
  \DataTypeTok{int}\NormalTok{ lztar}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{int}\NormalTok{ fa}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \DataTypeTok{void}\NormalTok{ dfs0}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ o}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ f}\OperatorTok{)\{}
  \NormalTok{    fa}\OperatorTok{[}\NormalTok{o}\OperatorTok{]} \OperatorTok{=}\NormalTok{ f}\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{ node }\OperatorTok{=}\NormalTok{ edge}\OperatorTok{[}\NormalTok{i}\OperatorTok{].}\NormalTok{node}\OperatorTok{;}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{node }\OperatorTok{==}\NormalTok{ f}\OperatorTok{)} \ControlFlowTok{continue}\OperatorTok{;}
  \NormalTok{        dfs0}\OperatorTok{(}\NormalTok{node}\OperatorTok{,}\NormalTok{ o}\OperatorTok{);}
      \OperatorTok{\}}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ V}\OperatorTok{[}\NormalTok{\_}\OperatorTok{];}
  \KeywordTok{inline} \DataTypeTok{int}\NormalTok{ get}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{==} \OperatorTok{{-}}\DecValTok{1} \OperatorTok{?} \DecValTok{0} \OperatorTok{:}\NormalTok{ lztar}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]])} \OperatorTok{+}\NormalTok{ V}\OperatorTok{[}\NormalTok{x}\OperatorTok{];} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()}
  \OperatorTok{\{}
  \PreprocessorTok{\#ifdef LOCAL\_JUDGE}
  \CommentTok{//    freopen("in.in", "r", stdin);}
  \CommentTok{//    freopen("out.txt", "w", stdout);}
  \PreprocessorTok{\#endif}
  \CommentTok{//  freopen("in.in", "r", stdin);}
      \DataTypeTok{clock\_t}\NormalTok{ c1 }\OperatorTok{=}\NormalTok{ clock}\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{++)\{}
          \DataTypeTok{int}\NormalTok{ u }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();} \CommentTok{//read();}
  \NormalTok{        add}\OperatorTok{(}\NormalTok{u}\OperatorTok{,}\NormalTok{ v}\OperatorTok{);}\NormalTok{ add}\OperatorTok{(}\NormalTok{rt }\OperatorTok{=}\NormalTok{ v}\OperatorTok{,}\NormalTok{ u}\OperatorTok{);}
      \OperatorTok{\}}
  \CommentTok{//    show(rt);}
  \NormalTok{    dfs0}\OperatorTok{(}\NormalTok{rt}\OperatorTok{,} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{);}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{i}\OperatorTok{++)} \OperatorTok{\{}\NormalTok{ V}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{=}\NormalTok{ read}\OperatorTok{();} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{!=} \OperatorTok{{-}}\DecValTok{1}\OperatorTok{)}\NormalTok{trie}\OperatorTok{::}\NormalTok{insert}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{i}\OperatorTok{]],}\NormalTok{ V}\OperatorTok{[}\NormalTok{i}\OperatorTok{],} \DecValTok{0}\OperatorTok{);}  \OperatorTok{\}}
  \CommentTok{//    puts("OK");}
      \ControlFlowTok{while}\OperatorTok{(}\NormalTok{m}\OperatorTok{{-}{-})\{}
          \DataTypeTok{int}\NormalTok{ opt }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ x }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();} \CommentTok{//cerr \textless{}\textless{} "opt = " \textless{}\textless{} opt \textless{}\textless{} endl;}
  \CommentTok{//        if(get(x) \textless{} 0) puts("data error");}
          \ControlFlowTok{if}\OperatorTok{(}\NormalTok{opt }\OperatorTok{==} \DecValTok{1}\OperatorTok{)\{}
  \NormalTok{            lztar}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{++;} \CommentTok{//cerr \textless{}\textless{} "add lztar[ " \textless{}\textless{} x \textless{}\textless{} " ]" \textless{}\textless{} endl;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{!=}\NormalTok{ rt}\OperatorTok{)} \OperatorTok{\{}
                  \ControlFlowTok{if}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]])}\NormalTok{trie}\OperatorTok{::}\NormalTok{erase}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]]],}\NormalTok{ get}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]),} \DecValTok{0}\OperatorTok{);}
  \NormalTok{                V}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]]} \OperatorTok{++;}
                  \ControlFlowTok{if}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]])}\NormalTok{trie}\OperatorTok{::}\NormalTok{insert}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]]],}\NormalTok{ get}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]),} \DecValTok{0}\OperatorTok{);}
              \OperatorTok{\}}
  \NormalTok{            trie}\OperatorTok{::}\NormalTok{addall}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{x}\OperatorTok{]);}
          \OperatorTok{\}} \ControlFlowTok{else} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{opt }\OperatorTok{==} \DecValTok{2}\OperatorTok{)\{}
              \DataTypeTok{int}\NormalTok{ v }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{!=}\NormalTok{ rt}\OperatorTok{)}\NormalTok{ trie}\OperatorTok{::}\NormalTok{erase}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]],}\NormalTok{ get}\OperatorTok{(}\NormalTok{x}\OperatorTok{),} \DecValTok{0}\OperatorTok{);}
  \NormalTok{            V}\OperatorTok{[}\NormalTok{x}\OperatorTok{]} \OperatorTok{{-}=}\NormalTok{ v}\OperatorTok{;}
              \ControlFlowTok{if}\OperatorTok{(}\NormalTok{x }\OperatorTok{!=}\NormalTok{ rt}\OperatorTok{)}\NormalTok{ trie}\OperatorTok{::}\NormalTok{insert}\OperatorTok{(}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]],}\NormalTok{ get}\OperatorTok{(}\NormalTok{x}\OperatorTok{),} \DecValTok{0}\OperatorTok{);}
          \OperatorTok{\}} \ControlFlowTok{else} \OperatorTok{\{}
              \DataTypeTok{int}\NormalTok{ res }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
  \NormalTok{            res }\OperatorTok{=}\NormalTok{ trie}\OperatorTok{::}\NormalTok{xorv}\OperatorTok{[}\NormalTok{trie}\OperatorTok{::}\NormalTok{rt}\OperatorTok{[}\NormalTok{x}\OperatorTok{]];}
  \NormalTok{            res }\OperatorTok{\^{}=}\NormalTok{ get}\OperatorTok{(}\NormalTok{fa}\OperatorTok{[}\NormalTok{x}\OperatorTok{]);}
  \NormalTok{            printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%d\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ res}\OperatorTok{);}
          \OperatorTok{\}}
      \OperatorTok{\}}
      \BuiltInTok{std::}\NormalTok{cerr }\OperatorTok{\textless{}\textless{}} \StringTok{"}\SpecialCharTok{\textbackslash{}n\textbackslash{}n}\StringTok{Time:  "} \OperatorTok{\textless{}\textless{}}\NormalTok{ clock}\OperatorTok{()} \OperatorTok{{-}}\NormalTok{ c1 }\OperatorTok{\textless{}\textless{}} \StringTok{"  ms"} \OperatorTok{\textless{}\textless{}} \BuiltInTok{std::}\NormalTok{endl}\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 132.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 162.
  
  [1] [2] [3] [4] [5] (.../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 (5 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 132.
  
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 162.
  
  [1] [2] [3] [4] [5] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (5 pages).
  Transcript written on .../input.log.

「杂题记录」「YuGu P6623」「省选联考 2020 A 卷」 树