fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long
  5. const int N=2e5+5;
  6. int n,q,s[N],heavy[N],root[N],dep[N],par[N],sz[N],pos[N],timer;
  7. vector<int>adj[N];
  8. void dfs_size(int node,int p)
  9. {
  10.     par[node]=p;
  11.     dep[node]=dep[p]+1;
  12.     sz[node]=1;
  13.     int bigc=-1,bigv=-1;
  14.     for(auto it:adj[node])
  15.     {
  16.         if(it!=p)
  17.         {
  18.             dfs_size(it,node);
  19.             sz[node]+=sz[it];
  20.             if(sz[it]>bigv)
  21.             {
  22.                 bigv=sz[it];
  23.                 bigc=it;
  24.             }
  25.         }
  26.     }
  27.     heavy[node]=bigc;
  28. }
  29. void dfs_positions(int node,int p)
  30. {
  31.     pos[node]=timer++;
  32.     if(~heavy[node])
  33.     {
  34.         dfs_positions(heavy[node],node);
  35.     }
  36.     for(auto it:adj[node])
  37.     {
  38.         if(it!=p&&it!=heavy[node])
  39.         {
  40.             dfs_positions(it,node);
  41.         }
  42.     }
  43. }
  44. void dfs_chain(int node,int p)
  45. {
  46.     if(~heavy[node])
  47.     {
  48.         root[heavy[node]]=root[node];
  49.     }
  50.     for(auto it:adj[node])
  51.     {
  52.         if(it!=p)
  53.         {
  54.             dfs_chain(it,node);
  55.         }
  56.     }
  57. }
  58. void init()
  59. {
  60.     iota(root,root+N,0);
  61.     memset(heavy,-1,sizeof heavy);
  62.     dfs_size(1,0);
  63.     dfs_chain(1,0);
  64.     dfs_positions(1,0);
  65. }
  66. struct SegmentTree{
  67. private:
  68. #define L 2*node+1
  69. #define R 2*node+2
  70. #define mid (l+r>>1)
  71.     struct Node{
  72.         ll cnt,inc;
  73.         Node(){}
  74.         Node(ll b,ll c):cnt(b),inc(c){}
  75.     };
  76.     ll sum(ll n)
  77.     {
  78.         return n*(n+1)/2;
  79.     }
  80.     int sz;vector<ll>seg;vector<Node>lazy;
  81.     void propegate(int l,int r,int node)
  82.     {
  83.         if(lazy[node].cnt==0) return;
  84.         if(l!=r)
  85.         {
  86.             lazy[L].cnt+=lazy[node].cnt;
  87.             lazy[L].inc+=lazy[node].inc;
  88.             lazy[R].cnt+=lazy[node].cnt+(mid-l+1)*lazy[node].inc;
  89.             lazy[R].inc+=lazy[node].inc;
  90.         }
  91.         ll len=r-l+1;
  92.         seg[node]+=lazy[node].cnt*len;
  93.         seg[node]+=lazy[node].inc*sum(len-1);
  94.         lazy[node]=Node(0,0);
  95.     }
  96.     void add(int l,int r,int node,int lx,int rx,ll start,ll zeyada)
  97.     {
  98.         propegate(l,r,node);
  99.         if(l>rx||r<lx)
  100.         {
  101.             return;
  102.         }
  103.         if(l>=lx&&r<=rx)
  104.         {
  105.             lazy[node].inc+=zeyada;
  106.             lazy[node].cnt+=start+(l-lx)*zeyada;
  107.             propegate(l,r,node);
  108.             return;
  109.         }
  110.         add(l,mid,L,lx,rx,start,zeyada);
  111.         add(mid+1,r,R,lx,rx,start,zeyada);
  112.         seg[node]=seg[L]+seg[R];
  113.     }
  114.     ll query(int l,int r,int node,int lx,int rx)
  115.     {
  116.         propegate(l,r,node);
  117.         if(l>rx||r<lx)
  118.         {
  119.             return 0;
  120.         }
  121.         if(l>=lx&&r<=rx)
  122.         {
  123.             return seg[node];
  124.         }
  125.         return query(l,mid,L,lx,rx)+query(mid+1,r,R,lx,rx);
  126.     }
  127. public:
  128.     SegmentTree(int n)
  129.     {
  130.         sz=1;
  131.         while(sz<n)
  132.         {
  133.             sz<<=1;
  134.         }
  135.         seg=vector<ll>(sz<<1);
  136.         lazy=vector<Node>(sz<<1,Node(0,0));
  137.     }
  138.     void add(int l,int r,ll start,ll zeyada)
  139.     {
  140.         add(0,sz-1,0,l,r,start,zeyada);
  141.     }
  142.     ll query(int l,int r)
  143.     {
  144.         return query(0,sz-1,0,l,r);
  145.     }
  146. #undef L
  147. #undef R
  148. #undef mid
  149. }tree(N);
  150. int dis(int u,int v)
  151. {
  152.     ll ret=0;
  153.     while(root[u]!=root[v])
  154.     {
  155.         if(dep[root[u]]>dep[root[v]])
  156.         {
  157.             swap(u,v);
  158.         }
  159.         ret+=pos[root[v]]-pos[v]+1;
  160.         v=par[root[v]];
  161.     }
  162.     if(dep[u]>dep[v])
  163.     {
  164.         swap(u,v);
  165.     }
  166.     ret+=pos[v]-pos[u]+1;
  167.     return ret;
  168. }
  169. void update(int u,int v)
  170. {
  171.     int L=1,R=dis(u,v);
  172.     while(root[u]!=root[v])
  173.     {
  174.         if(dep[root[u]]>dep[root[v]])
  175.         {
  176.             int len=pos[u]-pos[root[u]]+1;
  177.             tree.add(pos[root[u]],pos[u],L,1);
  178.             L+=len;
  179.             u=par[root[u]];
  180.         }
  181.         else
  182.         {
  183.             int len=pos[v]-pos[root[v]]+1;
  184.             tree.add(pos[root[v]],pos[v],R,-1);
  185.             R-=len;
  186.             v=par[root[v]];
  187.         }
  188.     }
  189.     if(dep[u]>dep[v])
  190.     {
  191.         tree.add(pos[v],pos[u],R,-1);
  192.     }
  193.     else
  194.     {
  195.         tree.add(pos[u],pos[v],L,1);
  196.     }
  197. } // في شغل هنا
  198. int query(int u,int v)
  199. {
  200.     ll ret=0;
  201.     while(root[u]!=root[v])
  202.     {
  203.         if(dep[root[u]]>dep[root[v]])
  204.         {
  205.             swap(u,v);
  206.         }
  207.         ret+=tree.query(pos[root[v]],pos[v]);
  208.         v=par[root[v]];
  209.     }
  210.     if(dep[u]>dep[v])
  211.     {
  212.         swap(u,v);
  213.     }
  214.     ret+=tree.query(pos[u],pos[v]);
  215.     return ret;
  216. }
  217. signed main()
  218. {
  219.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  220.     cin>>n;
  221.     for(int i=0;i<n-1;i++)
  222.     {
  223.         int a,b;cin>>a>>b;
  224.         adj[a].push_back(b);
  225.         adj[b].push_back(a);
  226.     }
  227.     init();
  228.     cin>>q;while(q--)
  229.     {
  230.         int op;cin>>op;
  231.         if(op==1)
  232.         {
  233.             int u,v;cin>>u>>v;
  234.             update(u,v);
  235.         }
  236.         else if(op==2)
  237.         {
  238.             int u,v;cin>>u>>v;
  239.             cout<<query(u,v)<<'\n';
  240.         }
  241.     }
  242.     return 0;
  243. }
Success #stdin #stdout 0.01s 29740KB
comments (?)
stdin
copy 
10
1 2
1 8
4 2
4 5
2 3
6 5
6 7
9 2
10 4
13
1 9 1
1 6 9
2 6 2
1 6 4
2 10 9
1 10 9
2 7 1
1 10 3
2 6 5
1 6 8
1 6 4
2 6 1
2 4 1
stdout
copy 
12
18
26
6
52
40
https://ideone.com/FA4maZ
language:
C++14 (gcc 8.3)
created:
34 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!