e-mon

備忘録

ABC014(C,D)

ARC039の復習で,適当な根付き木にして距離を出す必要があったのでライブラリのチェックのために解いた. Dの閉路だけ通すつもりだったけど,どうせなら,とC問題も解いた.

C : AtColor

与えられた区間の最も重なる点を求める問題.

いもす法.気をつけなきゃいけないのは,与えられているのが閉区間なので一個ずれる. 106 かかるのでPythonで通るのか少し不安だったけど,制限時間3秒だったのでセーフ.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
info = [0 for i in range(10**6 + 2)]
for _ in range(n):
    a,b =  map(int,input().split())
    info[a] += 1
    info[b+1] -= 1

for i in range(10**6 + 1):
    info[i + 1] += info[i]

print(max(info))

D:閉路

 1 \le N \le 10^5 , 1 \le Q \le 10^5

木が与えられていて,ある辺を加えたときに生じる閉路の長さを答える問題.

DFSにて深さ,親を記憶していきDFS木を構成する.よく解説に適当な根付き木にする,とあるけどたぶんこの適当な頂点からDFSで木を構成することを適当な根付き木にする,という意味だと思っている.

問題としては,与えられた辺をつなぐ頂点間の距離を元の木から求める事ができれば,追加分の辺を足してあげるだけで解ける.ただし,頂点が  10^5, クエリが 10^5 あるので,愚直に距離を求めると到底間に合わないので, dist(a,b) = depth(a) - depth(lca(a,b)) + depth(b) - depth(lca(a,b)) を用いて計算する.

ある頂点aとbのLCAを求める方法は,一番簡単な方法だと同じ高さにして1つずつ親をたどっていく方法だけど,この方法だとO(N)となり,Query分やってしまうとTLE.なので, O(log(N)LCAを求める事ができるダブリングを実装した.

初期化で行っているのはダブリングの前処理で,あるノードから  2^i たどった位置の親を記録している.ダブリングてのは,よくわかってないけど,LCAのようにある点からは共通しているような配列集合を2の累乗ごとに辿れるようにしておいて,配列同士の共通点までの二分探索をしやすくするためのものだと思っている.詳しくは以下.

参考 : [木に対する一般的なテク達] (http://t.co/yxsOVMIwRs)

Pythonで書きたかったので以下のようなクラスを作成した.

class RootedTree:
    # G : adjcency list : 0 - indexed
    # N : the number of vertex
    def __init__(self,N,G):
        self.N = N
        self.G = G

        # for lca
        self.log_N = 20

        self.parents = [[ -1 for i in range(self.log_N)] for j in range(N)]
        self.depth = [-1] * self.N
        self.tree_initialize(0)

        for i in range(self.log_N-1):
            for j in range(N):
                if self.parents[j][i] == -1:
                    self.parents[j][i+1] = -1
                else:
                    self.parents[j][i+1] = self.parents[self.parents[j][i]][i]

    def tree_initialize(self, u):
        q = []
        q.append((u,-1,0))
        while q != []:
            u,parent,d = q.pop()

            self.depth[u] = d
            self.parents[u][0] = parent
            for v in self.G[u]:
                if v != parent:
                    q.append((v, u, d+1))

    def lca(self, u, v):
        if(self.depth[v] < self.depth[u]):
            u,v = v,u

        for i in range(self.log_N-1)[::-1]:
            if(((self.depth[v] - self.depth[u])>>i)&1):
                v = self.parents[v][i]

        if u==v:
            return u

        for i in range(self.log_N-1)[::-1]:
            if self.parents[u][i] != self.parents[v][i]:
                u = self.parents[u][i]
                v = self.parents[v][i]

        return self.parents[u][0]
    
    def dist(self, u, v):
        l = self.lca(u,v)
        return (self.depth[u] - self.depth[l]) + (self.depth[v] - self.depth[l])

と,以上のように書いたはいいけど,結局 O(NlogN)だと 10^6を超えてしまうのでPythonではTLEだった.なので,C++で書きなおしてAC.

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9

struct rootedtree{
    int V;
    vector<vector<int> > T;
    vector<vector<int> > parents;
    vector<int> depth;
    int log_N = 20;

    rootedtree(int N, vector<vector<int> > &Tree){
        V = N;
        T = Tree;

        depth = vector<int>(V,0);
        parents = vector<vector<int> >(V, vector<int>(log_N-1,0));
        dfs(0,-1,0);

        FOR(i,0,log_N-1){
            FOR(j,0,V){
                if(parents[j][i] == -1)
                    parents[j][i+1] = -1;
                else
                    parents[j][i+1] = parents[parents[j][i]][i];
            }
        }
    }

    void dfs(int u,int parent,int d){
        depth[u] = d;
        parents[u][0] = parent;
        for(int v : T[u]){
            if(v != parent)
                dfs(v, u, d + 1);
        }
    }

    int lca(int u, int v){
        if(depth[v] < depth[u])
            swap(u,v);
         
        for(int i=log_N-1;i>=0;i--){
            if(((depth[v] - depth[u])>>i)&1)
                v = parents[v][i];
         }

        if(u==v) return u;

        for(int i=log_N-1;i>=0;i--){
            if(parents[u][i] != parents[v][i]){
                u = parents[u][i];
                v = parents[v][i];
            }
        }
        
        return parents[u][0];
    }

    int dist(int u, int v){
        int l = lca(u,v);
        return (depth[u] - depth[l]) + (depth[v] - depth[l]);
    }
};

int main(){
    int N;
    int Q;
    cin >> N ;
    vector<vector<int> > T(N);
    FOR(i,0,N-1){
        int x,y;
        cin >> x >> y ;
        x--;y--;
        T[x].push_back(y);
        T[y].push_back(x);
    }

    rootedtree rt(N,T);

    cin >> Q ;
    FOR(i,0,Q){
        int a,b;
        cin >> a >> b ;
        a--;b--;
        cout << rt.dist(a,b) + 1 << endl;
    }

    return 0;
}