結果

問題 No.399 動的な領主
ユーザー char134217728char134217728
提出日時 2018-01-11 16:55:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,223 bytes
コンパイル時間 3,132 ms
コンパイル使用メモリ 232,556 KB
実行使用メモリ 37,632 KB
最終ジャッジ日時 2024-06-06 05:35:20
合計ジャッジ時間 10,647 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:195:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  195 | main(){
      | ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 200005;

struct HL{
  int root;
  vi head, heavy, weight, parent, sid;
  vvi *G, pl;
  map<int, int> hid;
  void dfs(int pos, int pre){
    weight[pos] = 1;
    heavy[pos] = -1;
    parent[pos] = pre;
    head[pos] = pos;
    int mw = 0, w;
    each(itr, (*G)[pos]){
      if(pre == *itr) continue;
      dfs(*itr, pos);
      w = weight[*itr];
      if(w > mw) mw = w, heavy[pos] = *itr;
      weight[pos] += w;
    }
  }
  void set_head(int pos, int pre){
    if(pos == head[pos]) hid[pos] = sz(hid)-1;
    pl[head[pos]].pb(pos);
    each(itr, (*G)[pos]){
      if(pre == *itr) continue;
      if(heavy[pos] == *itr){
        head[*itr] = head[pos];
        sid[*itr] = sid[pos] + 1;
      }
      set_head(*itr, pos);
    }
  }
  struct LCA{
    int ln;
    vvi *G, parent;
    vi depth;
    void dfs(int pos, int pre, int d){
      depth[pos] = d;
      each(itr, (*G)[pos]){
        if(pre == *itr) continue;
        parent[0][*itr] = pos;
        dfs(*itr, pos, d+1);
      }
    }
    int root(int a, int b){
      if(depth[a] > depth[b]) swap(a, b);
      int d = depth[b] - depth[a];
      FOR(i, 0, ln) if((1<<i)&d) b = parent[i][b];
      if(a == b) return a;
      FORR(i, ln-1, 0) if(parent[i][a] != parent[i][b]) a = parent[i][a], b = parent[i][b];
      return parent[0][a];
    }
    void build(vvi* G, int r){
      this->G = G;
      int n = sz(*G);
      for(ln = 0; (1<<ln) < n; ln++);
      parent = vvi(n);
      FOR(i, 0, ln) parent[i] = vi(n);
      depth = vi(n);
      dfs(r, -1, 0);
      FOR(i, 1, ln)FOR(j, 0, n) parent[i][j] = (parent[i-1][j] == -1 ? -1 : parent[i-1][parent[i-1][j]]);
    }
  };
  LCA lca;
  pair<pii, pii> path(int root, int leaf){ // [root, leaf] => head_id, is_last, idx_l, idx_r
    if(head[root] == head[leaf]) return mp(mp(hid[head[root]], -1), mp(sid[root], sid[leaf]));
    return mp(mp(hid[head[leaf]], parent[head[leaf]]), mp(sid[head[leaf]], sid[leaf]));
  }
  void build(vvi* G, int r){
    this->G = G;
    lca.build(G, r);
    int n = sz(*G);
    head = vi(n);
    heavy = vi(n);
    weight = vi(n);
    parent = vi(n);
    sid = vi(n);
    pl = vvi(n);
    dfs(r, -1);
    set_head(r, -1);
  }
};

struct StarrySky{
  typedef ll T1; typedef ll T2;
  const T1 e_merge = 0;
  const T2 e_add = 0;
  T1 merge(T1 a, T1 b){
    return a+b;
  }
  T1 addT1(T1 a, int k, int l, int r, T2 b){
    return a+b*(r-l);
  }
  T2 addT2(T2 a, T2 b){
    return a+b;
  }
//###################################################
  int n;
  vector<T1> d;
  vector<T2> s;
  void init(int m){
    n = 1<<(32-__builtin_clz(m-1));
    d.resize(2*n-1);
    s.resize(2*n-1);
    fill(d.begin(), d.end(), e_merge);
    fill(s.begin(), s.end(), e_add);
  }
  void init(vector<T1>&v){
    init(v.size());
    for(int j=0; j<v.size(); j++) d[j+n-1] = v[j];
    for(int j=n-2; j>=0; j--) d[j] = merge(d[j*2+1], d[j*2+2]);
  }
  void ref(int k, int l, int r){
    if(s[k] != e_add){
      int mid = (l+r)/2, _k = k*2+1;
      s[_k] = addT2(s[_k], s[k]);
      d[_k] = addT1(d[_k], _k, l, mid, s[k]);
      _k++;
      s[_k] = addT2(s[_k], s[k]);
      d[_k] = addT1(d[_k], _k, mid, r, s[k]);
      s[k] = e_add;
    }
  }
  T1 _section_add(int a,int b,int k,int l,int r, T2&v){
    if(r<=a||b<=l){
    }else if(a<=l&&r<=b){
      s[k] = addT2(s[k], v);
      d[k] = addT1(d[k], k, l, r, v);
    }else{
      ref(k, l, r);
      d[k] = merge(_section_add(a, b, k*2+1, l, (l+r)/2, v), _section_add(a, b, k*2+2, (l+r)/2, r, v));
    }
    return d[k];
  }
  void section_add(int a, int b, T2 v){
    _section_add(a, b, 0, 0, n, v);
  }
  T1 _query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return e_merge;
    if(a<=l&&r<=b) return d[k];
    ref(k, l, r);
    return merge(_query(a, b, k*2+1, l, (l+r)/2), _query(a, b, k*2+2, (l+r)/2, r));
  }
  T1 query(int a,int b){
    return _query(a, b, 0, 0, n);
  }
};
vector<StarrySky> vss;
HL hl;
int n, q, x, y;
vvi G;

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  G.resize(n);
  FOR(i, 0, n-1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].pb(b);
    G[b].pb(a);
  }
  hl.build(&G, 0);
  vss.resize(sz(hl.hid));
  each(itr, hl.hid){
    vl s = vl(sz(hl.pl[itr->fi]));
    vss[itr->se].init(s);
  }
  cin >> q;
  pair<pii, pii> t;
  ll ans = 0;
  FOR(i, 0, q){
    cin >> x >> y;
    x--; y--;
    int r = hl.lca.root(x, y);
    while(true){
      t = hl.path(r, x);
      vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1);
      ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1);
      if(t.fi.se == -1) break;
      x = t.fi.se;
    }
    while(true){
      t = hl.path(r, y);
      vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1);
      ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1);
      if(t.fi.se == -1) break;
      y = t.fi.se;
    }
    t = hl.path(r, r);
    ans -= vss[t.fi.fi].query(t.se.fi, t.se.se+1);
    vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, -1);
  }
  cout << ans << endl;
  return 0;
}
0