fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) (int)v.size()
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(5e5)+7;
  14. const int LOG = 20;
  15.  
  16. int n , q , a[maxN]; string s;
  17. vector<int> g[maxN];
  18. int d[maxN] , in[maxN] , out[maxN] , DfsTime = 0 , fa[maxN];
  19. int p[maxN] , h[maxN] , sz[maxN] , numChain = 0 , numPos = 0 , chain[maxN] , pos[maxN] , head[maxN];
  20.  
  21. void dfs(int u){
  22.     d[u] = d[p[u]] + a[u];
  23.     in[u] = ++DfsTime;
  24.     sz[u] = 1;
  25.     for (int v : g[u]){
  26.         if (v != p[u]){
  27.             p[v] = u;
  28.             h[v] = h[u] + 1;
  29.             dfs(v);
  30.             sz[u] += sz[v];
  31.         }
  32.     }
  33.     out[u] = DfsTime;
  34. }
  35.  
  36. void hld(int u){
  37.     if (head[numChain] == 0) head[numChain] = u;
  38.     chain[u] = numChain;
  39.     pos[u] = ++numPos;
  40.     int heavy = -1;
  41.     for (int v : g[u]){
  42.         if (v != p[u] && (heavy == -1 || sz[heavy] < sz[v])) heavy = v;
  43.     }
  44.     if (heavy != -1) hld(heavy);
  45.     for (int v : g[u]){
  46.         if (v != p[u] && v != heavy){
  47.             numChain++;
  48.             hld(v);
  49.         }
  50.     }
  51. }
  52.  
  53. int lca(int u , int v){
  54.     while (chain[u] != chain[v]){
  55.         if (h[head[chain[u]]] > h[head[chain[v]]]) swap(u , v);
  56.         v = p[head[chain[v]]];
  57.     }
  58.     if (h[u] > h[v]) swap(u , v);
  59.     return u;
  60. }
  61.  
  62. struct fenwick{
  63.     int t[maxN];
  64.  
  65.     void reset(){
  66.         for (int i = 1 ; i <= n ; i++) t[i] = 0;
  67.     }
  68.  
  69.     void update(int x , int y){
  70.         for (; x <= n ; x += x&-x) t[x] += y;
  71.     }
  72.  
  73.     void update(int l , int r , int x){
  74.         update(l , +x);
  75.         update(r + 1 , -x);
  76.     }
  77.  
  78.     int get(int x){
  79.         int ans = 0;
  80.         for (; x >= 1 ; x -= x&-x) ans += t[x];
  81.         return ans;
  82.     }
  83. } fen;
  84.  
  85. ii E[maxN];
  86. int res[maxN];
  87. vector<int> event[2 * maxN] , query[2 * maxN];
  88.  
  89. void TH1(){
  90.     for (int i = 1 ; i <= n ; i++){
  91.         event[d[p[i]] + maxN].push_back(i);
  92.     }
  93.     for (int i = 1 ; i <= q ; i++){
  94.         query[d[E[i].fi] + maxN].push_back(i);
  95.     }
  96.     for (int i = -n ; i <= +n ; i++){
  97.         for (int id : query[i + maxN]){
  98.             int u = E[id].fi;
  99.             int v = E[id].se;
  100.             int x = fa[id];
  101.             res[id] += fen.get(in[u]) - fen.get(in[p[x]]);
  102.         }
  103.         for (int id : event[i + maxN]){
  104.             fen.update(in[id] , out[id] , +1);
  105.         }
  106.     }
  107. }
  108.  
  109. void TH2(){
  110.     for (int i = -n ; i <= +n ; i++) event[i + maxN].clear() , query[i + maxN].clear();
  111.     fen.reset();
  112.     for (int i = 1 ; i <= n ; i++){
  113.         event[d[i] + maxN].push_back(i);
  114.     }
  115.     for (int i = 1 ; i <= q ; i++){
  116.         int u = E[i].fi;
  117.         int v = E[i].se;
  118.         int x = fa[i];
  119.         query[d[p[x]] - (d[u] - d[x]) + maxN].push_back(i);
  120.     }
  121.     for (int i = +n ; i >= -n ; i--){
  122.         for (int id : query[i + maxN]){
  123.             int u = E[id].fi;
  124.             int v = E[id].se;
  125.             int x = fa[id];
  126.             res[id] += fen.get(in[v]) - fen.get(in[p[x]]);
  127.             if (d[u] - d[p[x]] > 0) res[id]--;
  128.         }
  129.         for (int id : event[i + maxN]){
  130.             fen.update(in[id] , out[id] , +1);
  131.         }
  132.     }
  133. }
  134.  
  135. void solve(){
  136.     cin >> n >> q >> s;
  137.     s = '#' + s;
  138.     for (int i = 1 ; i <= n ; i++) a[i] = (s[i] == '+') ? +1 : -1;
  139.     for (int i = 1 ; i < n ; i++){
  140.         int u , v;
  141.         cin >> u >> v;
  142.         g[u].push_back(v);
  143.         g[v].push_back(u);
  144.     }
  145.     d[0] = 0;
  146.     dfs(1);
  147.     hld(1);
  148.     for (int i = 1 ; i <= q ; i++){
  149.         int u , v;
  150.         cin >> u >> v;
  151.         E[i] = {u , v};
  152.         fa[i] = lca(u , v);
  153.     }
  154.     TH1();
  155.     TH2();
  156.     for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n";
  157. }
  158.  
  159. #define name "A"
  160.  
  161. int main(){
  162.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  163.     // freopen(name".inp" , "r" , stdin);
  164.     // freopen(name".out" , "w" , stdout);
  165.     int t = 1; //cin >> t;
  166.     while (t--) solve();
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0.02s 73108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ou3fc4
language:
C++14 (gcc 8.3)
created:
6 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!