結果

問題 No.399 動的な領主
ユーザー mamekinmamekin
提出日時 2016-10-08 00:10:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 222 ms / 2,000 ms
コード長 4,287 bytes
コンパイル時間 1,512 ms
コンパイル使用メモリ 124,620 KB
実行使用メモリ 23,168 KB
最終ジャッジ日時 2024-11-21 20:01:29
合計ジャッジ時間 5,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

template <class T>
class EdgeBase
{
public:
    int to;
    T cost;
    EdgeBase(){};
    EdgeBase(int to0, T cost0){to = to0; cost = cost0;}
};
typedef EdgeBase<int> Edge;

template<class T>
class LowestCommonAncestor
{
private:
    vector<vector<int> > to; // ダブリング先のノード
    vector<int> depth;       // 根からの深さ
    vector<T> dist;          // 根からの距離
public:
    int climb(int curr, int len)
    {
        int i = 0;
        while(len > 0){
            if(len % 2 == 1)
                curr = to[curr][i];
            len /= 2;
            ++ i;
        }
        return curr;
    }
    LowestCommonAncestor(const vector<vector<EdgeBase<T> > >& edges, int root)
    {
        int n = edges.size();
        to.assign(n, vector<int>());
        dist.assign(n, 0);
        depth.assign(n, 0);

        queue<pair<int, int> > q;
        q.push(make_pair(root, -1));

        int cnt = 0;
        while(!q.empty()){
            int m = q.size();
            while(--m >= 0){
                int curr, prev;
                tie(curr, prev) = q.front();
                q.pop();

                if(prev != -1){
                    to[curr].push_back(prev);
                    int j = prev;
                    for(unsigned k=0; k<to[j].size(); ++k){
                        j = to[j][k];
                        to[curr].push_back(j);
                    }
                }

                for(const EdgeBase<T>& e : edges[curr]){
                    if(e.to != prev){
                        depth[e.to] = depth[curr] + 1;
                        dist[e.to] = dist[curr] + e.cost;
                        q.push(make_pair(e.to, curr));
                    }
                }
            }
            ++ cnt;
        }
    }
    // 2つのノードの最小共通祖先を取得
    int getAncestor(int a, int b)
    {
        int diff = depth[a] - depth[b];
        if(diff < 0)
            b = climb(b, -diff);
        else
            a = climb(a, diff);
        if(a == b)
            return a;

        for(int i=to[a].size()-1; i>=0; --i){
            if(i < (int)to[a].size() && to[a][i] != to[b][i]){
                a = to[a][i];
                b = to[b][i];
            }
        }
        return to[a][0];
    }
    // ノードの深さを取得
    int getDepth(int a)
    {
        return depth[a];
    }
    // 2つのノードの距離を取得
    T getDist(int a, int b)
    {
        int c = getAncestor(a, b);
        return dist[a] + dist[b] - dist[c] * 2;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<vector<Edge> > edges(n);
    for(int i=0; i<n-1; ++i){
        int u, v;
        cin >> u >> v;
        -- u;
        -- v;
        edges[u].push_back(Edge(v, 1));
        edges[v].push_back(Edge(u, 1));
    }

    int root = 0;
    LowestCommonAncestor<int> lca(edges, root);

    int query;
    cin >> query;
    vector<int> cnt(n);
    while(--query >= 0){
        int a, b;
        cin >> a >> b;
        -- a;
        -- b;
        ++ cnt[a];
        ++ cnt[b];

        int c = lca.getAncestor(a, b);
        -- cnt[c];
        if(c != root){
            int d = lca.climb(c, 1);
            -- cnt[d];
        }
    }

    queue<int> q;
    vector<int> index;
    vector<int> parent(n, -1);
    q.push(root);
    index.push_back(root);
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(const Edge& e : edges[curr]){
            if(e.to != root && parent[e.to] == -1){
                q.push(e.to);
                index.push_back(e.to);
                parent[e.to] = curr;
            }
        }
    }
    for(int i=n-1; i>0; --i)
        cnt[parent[index[i]]] += cnt[index[i]];

    long long ans = 0;
    for(int i=0; i<n; ++i)
        ans += cnt[i] * (cnt[i] + 1LL) / 2;
    cout << ans << endl;

    return 0;
}
0