schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264
							<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  <title>树链剖分 | Schtonn&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="前置知识
 必备：存图方式（邻接表，邻接矩阵），dfs序。 维护：线段树、树状数组、BST。 不会的快进入链接学习吧！
 引入
 树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为\(O(log n)\)。">
<meta property="og:type" content="article">
<meta property="og:title" content="树链剖分">
<meta property="og:url" content="http://yoursite.com/2020/03/01/tree-link/index.html">
<meta property="og:site_name" content="Schtonn&#39;s Blog">
<meta property="og:description" content="前置知识
 必备：存图方式（邻接表，邻接矩阵），dfs序。 维护：线段树、树状数组、BST。 不会的快进入链接学习吧！
 引入
 树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为\(O(log n)\)。">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20191228195815530.png">
<meta property="article:published_time" content="2020-03-01T14:41:02.000Z">
<meta property="article:modified_time" content="2020-03-03T12:39:51.311Z">
<meta property="article:author" content="Schtonn">
<meta property="article:tag" content="graph">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/20191228195815530.png">
  
    <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Schtonn&#39;s Blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">Schtonn&#39;s blog</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-tree-link" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/tree-link/" class="article-date">
  <time datetime="2020-03-01T14:41:02.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      树链剖分
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>必备：存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="http://baidu.physton.com/?q=dfs%E5%BA%8F" target="_blank" rel="noopener">dfs序</a>。 维护：<a href="http://baidu.physton.com/?q=%E7%BA%BF%E6%AE%B5%E6%A0%91" target="_blank" rel="noopener">线段树</a>、<a href="http://baidu.physton.com/?q=%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84" target="_blank" rel="noopener">树状数组</a>、<a href="http://baidu.physton.com/?q=BST" target="_blank" rel="noopener">BST</a>。 不会的快进入链接学习吧！</p>
<h3 id="引入">引入</h3>
<p>树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为<span class="math inline">\(O(log n)\)</span>。 <a id="more"></a></p>
<h3 id="剖分方式">剖分方式</h3>
<p>对于每一个节点，它的子节点中<strong>子树的节点数最大的</strong>为重儿子，连接到重儿子的边称为重边。例如： <img src="https://img-blog.csdnimg.cn/20191228195815530.png" /> 加粗节点为重儿子。<span class="math inline">\(4\)</span><span class="math inline">\(5\)</span><span class="math inline">\(6\)</span>节点的重量都一样，所以你想上哪个成为重儿子那个就是重儿子。除重儿子和重边外的节点和边均为轻儿子或轻边。根不是重儿子也不是轻儿子 <del>，有脑子的人都会想一想，它根本就不是什么儿子！</del> 。 以轻儿子或者根为起点的，由重边连接的一条连续的链称为重链。特别地，若一个叶子结点是轻儿子，那么便有一条以该叶子结点为起点的长度为1的重链。上图中，<span class="math inline">\(1-3-7-9\)</span>是一条重链，<span class="math inline">\(6\)</span>一个节点也是一条重链。</p>
<h3 id="预处理">预处理</h3>
<p>树链剖分的预处理本质上就是2个dfs。</p>
<h4 id="dfs-no.1">dfs NO.1</h4>
<p>一共完成四项任务。 - 标记节点深度：<span class="math inline">\(dep[]\)</span> - 标记节点的父节点：<span class="math inline">\(fa[]\)</span> - 标记节点的子树大小：<span class="math inline">\(siz[]\)</span> - 标记节点的重儿子编号：<span class="math inline">\(son[]\)</span></p>
<p>代码： <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_1</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> f)</span></span>&#123;</span><br><span class="line">    siz[u]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> maxson=<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i!=<span class="number">-1</span>;i=edge[i].nxt)&#123;</span><br><span class="line">		<span class="keyword">int</span> v=edge[i].v;</span><br><span class="line">        <span class="keyword">if</span>(v==f) <span class="keyword">continue</span>;</span><br><span class="line">		fa[v]=u;</span><br><span class="line">		dep[v]=dep[u]+<span class="number">1</span>;</span><br><span class="line">		dfs_1(v,u);</span><br><span class="line">        siz[u]+=siz[v];</span><br><span class="line">        <span class="keyword">if</span>(siz[v]&gt;siz[son[u]])son[u]=v;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h4 id="dfs-no.2">dfs NO.2</h4>
<p>完成三项任务。 - 标记dfs序（先重后轻）：<span class="math inline">\(idx[]\)</span> - 标记dfs序对应的节点：<span class="math inline">\(rnk[]\)</span> - 标记节点所在重链的顶端：<span class="math inline">\(top[]\)</span></p>
<p>代码： <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_2</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> tp)</span></span>&#123;</span><br><span class="line">    idx[u]=++dfn;</span><br><span class="line">    rnk[dfn]=a[u];</span><br><span class="line">    top[u]=tp;</span><br><span class="line">    <span class="keyword">if</span>(!son[u])<span class="keyword">return</span>;</span><br><span class="line">    dfs_2(son[u],tp);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i!=<span class="number">-1</span>;i=edge[i].nxt)&#123;</span><br><span class="line">        <span class="keyword">if</span>(!idx[edge[i].v])&#123;</span><br><span class="line">            dfs_2(edge[i].v,edge[i].v);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="维护">维护</h3>
<p>这里以洛谷的<a href="https://www.luogu.com.cn/problem/P3384" target="_blank" rel="noopener">P3384</a>为例 要求维护四种操作： - 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z - 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 - 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z - 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和</p>
<ol type="1">
<li><p>要处理两点间的路径时： 首先找到两个节点中较深的那个点，然后将对该店所在链进行处理，并将该点移动至所在链顶端节点<strong>的父节点</strong>。因为是按照轻重边为优先级做的dfs，所以一条链上的编号一定是连续的。 循环执行直到两个点在一条链上，这时再处理两个点之间的区间即可。</p></li>
<li><p>要处理一个点的子树时： 因为是dfs序，所以子树的dfs序一定是连续的区间，直接处理该区间即可。</p></li>
</ol>
<p>因为都是处理区间，所以用线段树维护。</p>
<h3 id="完整代码">完整代码</h3>
<p>因为题目中还有一个毒瘤%p，所以代码显得很繁杂。 <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">"bits/stdc++.h"</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">2000100</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> lson id&lt;&lt;1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rson id&lt;&lt;1|1</span></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">read</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> c=<span class="number">1</span>,q=<span class="number">0</span>;<span class="keyword">char</span> ch=<span class="string">' '</span>;</span><br><span class="line">    <span class="keyword">while</span>(ch!=<span class="string">'-'</span>&amp;&amp;(ch&lt;<span class="string">'0'</span>||ch&gt;<span class="string">'9'</span>))ch=getchar();</span><br><span class="line">    <span class="keyword">if</span>(ch==<span class="string">'-'</span>)c=<span class="number">-1</span>,ch=getchar();</span><br><span class="line">    <span class="keyword">while</span>(ch&gt;=<span class="string">'0'</span>&amp;&amp;ch&lt;=<span class="string">'9'</span>)q=q*<span class="number">10</span>+ch-<span class="string">'0'</span>,ch=getchar();</span><br><span class="line">    <span class="keyword">return</span> c*q;</span><br><span class="line">&#125;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> u,v,nxt;</span><br><span class="line">&#125;e[N];</span><br><span class="line"><span class="keyword">int</span> head[N];</span><br><span class="line"><span class="keyword">int</span> tot=<span class="number">1</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Tree</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> l,r,c,siz,f;</span><br><span class="line">&#125;t[N];</span><br><span class="line"><span class="keyword">int</span> n,m,root,p,dfn=<span class="number">0</span>,rnk[N],a[N];</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    e[tot].u=x;</span><br><span class="line">    e[tot].v=y;</span><br><span class="line">    e[tot].nxt=head[x];</span><br><span class="line">    head[x]=tot++;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">int</span> dep[N],fa[N],son[N],siz[N],top[N],idx[N];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_1</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> f)</span></span>&#123;</span><br><span class="line">    siz[u]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].nxt)&#123;</span><br><span class="line">		<span class="keyword">int</span> v=e[i].v;</span><br><span class="line">        <span class="keyword">if</span>(v==f) <span class="keyword">continue</span>;</span><br><span class="line">		fa[v]=u;</span><br><span class="line">		dep[v]=dep[u]+<span class="number">1</span>;</span><br><span class="line">		dfs_1(v,u);</span><br><span class="line">        siz[u]+=siz[v];</span><br><span class="line">        <span class="keyword">if</span>(siz[v]&gt;siz[son[u]])son[u]=v;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> id)</span></span>&#123;</span><br><span class="line">    t[id].c=(t[lson].c+t[rson].c+p)%p;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Build</span><span class="params">(<span class="keyword">int</span> id,<span class="keyword">int</span> L,<span class="keyword">int</span> R)</span></span>&#123;</span><br><span class="line">    t[id].l=L;t[id].r=R;t[id].siz=R-L+<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(L==R)&#123;</span><br><span class="line">        t[id].c=rnk[L];</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> mid=(L+R)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    Build(lson,L,mid);</span><br><span class="line">    Build(rson,mid+<span class="number">1</span>,R);</span><br><span class="line">    update(id);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_2</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> tp)</span></span>&#123;</span><br><span class="line">    idx[u]=++dfn;</span><br><span class="line">    rnk[dfn]=a[u];</span><br><span class="line">    top[u]=tp;</span><br><span class="line">    <span class="keyword">if</span>(!son[u])<span class="keyword">return</span>;</span><br><span class="line">    dfs_2(son[u],tp);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].nxt)&#123;</span><br><span class="line">        <span class="keyword">if</span>(!idx[e[i].v])&#123;</span><br><span class="line">            dfs_2(e[i].v,e[i].v);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pushdown</span><span class="params">(<span class="keyword">int</span> id)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!t[id].f) <span class="keyword">return</span> ;</span><br><span class="line">    t[lson].c=(t[lson].c+t[lson].siz*t[id].f)%p;</span><br><span class="line">    t[rson].c=(t[rson].c+t[rson].siz*t[id].f)%p;</span><br><span class="line">    t[lson].f=(t[lson].f+t[id].f)%p;</span><br><span class="line">    t[rson].f=(t[rson].f+t[id].f)%p;</span><br><span class="line">    t[id].f=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addroute</span><span class="params">(<span class="keyword">int</span> id,<span class="keyword">int</span> L,<span class="keyword">int</span> R,<span class="keyword">int</span> c)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(L&lt;=t[id].l&amp;&amp;t[id].r&lt;=R)&#123;</span><br><span class="line">        t[id].c+=t[id].siz*c;</span><br><span class="line">        t[id].f+=c;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    pushdown(id);</span><br><span class="line">    <span class="keyword">int</span> mid=(t[id].l+t[id].r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(L&lt;=mid)addroute(lson,L,R,c);</span><br><span class="line">    <span class="keyword">if</span>(R&gt;mid)addroute(rson,L,R,c);</span><br><span class="line">    update(id);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addtree</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> c)</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(top[x]!=top[y])&#123;</span><br><span class="line">        <span class="keyword">if</span>(dep[top[x]]&lt;dep[top[y]])swap(x,y);</span><br><span class="line">        addroute(<span class="number">1</span>,idx[top[x]],idx[x],c);</span><br><span class="line">        x=fa[top[x]];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(dep[x]&gt;dep[y])swap(x,y);</span><br><span class="line">    addroute(<span class="number">1</span>,idx[x],idx[y],c);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sumroute</span><span class="params">(<span class="keyword">int</span> id,<span class="keyword">int</span> L,<span class="keyword">int</span> R)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(L&lt;=t[id].l&amp;&amp;t[id].r&lt;=R)</span><br><span class="line">        <span class="keyword">return</span> t[id].c;</span><br><span class="line">    pushdown(id);</span><br><span class="line">    <span class="keyword">int</span> mid=(t[id].l+t[id].r)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(L&lt;=mid) ans=(ans+sumroute(lson,L,R))%p;</span><br><span class="line">    <span class="keyword">if</span>(R&gt;mid)  ans=(ans+sumroute(rson,L,R))%p;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">treesum</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(top[x]!=top[y])&#123;</span><br><span class="line">        <span class="keyword">if</span>(dep[top[x]]&lt;dep[top[y]]) swap(x,y);</span><br><span class="line">        ans=(ans+sumroute(<span class="number">1</span>,idx[top[x]],idx[x]))%p;</span><br><span class="line">        x=fa[top[x]];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(dep[x]&gt;dep[y]) swap(x,y);</span><br><span class="line">    ans=(ans+sumroute(<span class="number">1</span>,idx[x],idx[y]))%p;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,ans);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    n=read();m=read();root=read();p=read();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) a[i]=read();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++)&#123;</span><br><span class="line">        <span class="keyword">int</span> x=read(),y=read();</span><br><span class="line">        add(x,y);add(y,x);</span><br><span class="line">    &#125;</span><br><span class="line">    dfs_1(root,root);</span><br><span class="line">    dfs_2(root,root);</span><br><span class="line">    Build(<span class="number">1</span>,<span class="number">1</span>,n);</span><br><span class="line">    <span class="keyword">while</span>(m--)&#123;</span><br><span class="line">        <span class="keyword">int</span> op=read(),x,y,z;</span><br><span class="line">        <span class="keyword">if</span>(op==<span class="number">1</span>)&#123;    </span><br><span class="line">            x=read();y=read();z=read();z=z%p;</span><br><span class="line">            addtree(x,y,z);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">2</span>)&#123;</span><br><span class="line">            x=read();y=read();</span><br><span class="line">            treesum(x,y);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">3</span>)&#123;</span><br><span class="line">            x=read(),z=read();</span><br><span class="line">            addroute(<span class="number">1</span>,idx[x],idx[x]+siz[x]<span class="number">-1</span>,z%p);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">4</span>)&#123;</span><br><span class="line">            x=read();</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,sumroute(<span class="number">1</span>,idx[x],idx[x]+siz[x]<span class="number">-1</span>));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> 完结撒花~~</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/tree-link/" data-id="ck7cjuv7b000bpc136ug4frq4" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2020/03/01/union-find/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          并查集
        
      </div>
    </a>
  
  
    <a href="/2020/03/01/plan/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">plan</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    </div>
  </div>

  
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/03/02/segment-tree/">线段树</a>
          </li>
        
          <li>
            <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
          </li>
        
          <li>
            <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
          </li>
        
          <li>
            <a href="/2020/03/01/min-span-tree/">最小生成树</a>
          </li>
        
          <li>
            <a href="/2020/03/01/union-find/">并查集</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 Schtonn<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>


  </div>
</body>
</html>