結果

問題 No.399 動的な領主
コンテスト
ユーザー yuki681
提出日時 2016-07-16 00:40:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 259 ms / 2,000 ms
コード長 2,915 bytes
コンパイル時間 2,225 ms
コンパイル使用メモリ 176,280 KB
実行使用メモリ 171,296 KB
最終ジャッジ日時 2024-11-07 19:19:11
合計ジャッジ時間 7,515 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define int long long int

using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, int> PPI;
typedef pair<int, PII> PIP;
typedef pair<PII, PII> PPP;
typedef vector<PII> VP;
typedef VP::iterator VPI;
typedef vector<int> VI;
const int INF = 3e18;
const double PI = acos(-1);

int n, q;
VI node[100001];
VI under[100001];
int a[100001], b[100001];
VP segarray;
int segnum[100001];
int pluss[100001], minuss[100001];
int ans = 0;

void input()
{
  scanf("%lld", &n);
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    scanf("%lld%lld", &u, &v);
    node[u].PB(v);
    node[v].PB(u);
  }

  scanf("%lld", &q);
  for(int i = 0; i < q; i++){
    scanf("%lld%lld", &a[i], &b[i]);
  }
}

void dfs(int parent, int x, int deep)
{
  segnum[x] = segarray.size();
  segarray.PB(MP(deep, x));
  for(int i = 0; i < node[x].size(); i++){
    if(node[x][i] != parent){
      under[x].PB(node[x][i]);
      dfs(x, node[x][i], deep + 1);
      segarray.PB(MP(deep, x));
    }
  }
}

struct segtree
{
  PII tree[9000000];
  int size;

  void reset()
  {
    size = 1;
    while(size < segarray.size()){
      size <<= 1;
    }

    set(0, size - 1, 0);
  }
  PII set(int left, int right, int now)
  {
    if(left == right){
      if(left >= segarray.size()){
	return tree[now] = MP(INF, INF);
      }
      else{
	return tree[now] = segarray[left];
      }	
    }
    else{
      return tree[now] = min(set(left, (left + right) / 2, now * 2 + 1), set((left + right) / 2 + 1, right, now * 2 + 2));
    }
  }

  PII smallest(int start, int end, int left, int right, int now)
  {
    if(right < start || end < left){
      return MP(INF, INF);
    }
    if(start <= left && right <= end){
      return tree[now];
    }
    return min(smallest(start, end, left, (left + right) / 2, now * 2 + 1), smallest(start, end, (left + right) / 2 + 1, right, now * 2 + 2));
  }
} lcm;

void compedge(int x)
{
  int lcma = segnum[a[x]], lcmb = segnum[b[x]];
  if(lcma > lcmb) swap(lcma, lcmb);
  PII lcmed = lcm.smallest(lcma, lcmb, 0, lcm.size - 1, 0);
  if(lcmed.second == a[x]){
    pluss[b[x]]++;
    minuss[a[x]]--;
  }
  else if(lcmed.second == b[x]){
    pluss[a[x]]++;
    minuss[b[x]]--;
  }
  else{
    pluss[a[x]]++;
    pluss[b[x]]++;
    pluss[lcmed.second]--;
    minuss[lcmed.second]--;
  }
}

int sumdp[200000];
int calcsum(int now)
{
  if(now == 0)
    return 0;
  if(sumdp[now] != -1)
    return sumdp[now];
  return sumdp[now] = now + calcsum(now - 1);
}

int solve(int now)
{
  int sum = 0;
  for(int i = 0; i < under[now].size(); i++){
    sum += solve(under[now][i]);
  }
  sum += pluss[now];
  ans += calcsum(sum);
  sum += minuss[now];
  return sum;
}

signed main()
{
  input();
  dfs(0, 1, 0);
  lcm.reset();
  for(int i = 0; i < q; i++){
    compedge(i);
  }
  memset(sumdp, -1, sizeof sumdp);
  solve(1);
  printf("%lld\n", ans);

  return 0;
}
0