Library/unauthenticated/AuxiliaryTree.hpp

• View this file on GitHub
• Last update: 2026-03-04 10:33:00+09:00
• Include: #include "Library/unauthenticated/AuxiliaryTree.hpp"

Depends on

• Library/Common.hpp
• Graph - グラフ構造 (Library/Graph/Graph.hpp)
• Lowest Common Ancestor - 最小共通祖先 (Library/Tree/LowestCommonAncestor.hpp)
• Tree - 木 (Library/Tree/Tree.hpp)
• Library/unauthenticated/EulerTour.hpp

Code

#include "../Tree/Tree.hpp"
#include "EulerTour.hpp"
#include "../Tree/LowestCommonAncestor.hpp"

template<typename WeightType>
class AuxiliaryTree{
    public:
    AuxiliaryTree(RootedTree<WeightType> &tree) :
            T(tree), lca_(tree), et_(tree), edge_cum_(CalculateTreeCumlativeSum(tree)){
    }

    void Set(const vector<Vertex> &vertex_set){
        auxiliary_tree_vertex_set_ = vertex_set;
        auxiliary_tree_size_ = auxiliary_tree_vertex_set_.size();
        sort(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end(), [&](int i, int j){
            return et_.get_in(i) < et_.get_in(j);
        });
        for(int i = 0; i < auxiliary_tree_size_ - 1; ++i){
            auxiliary_tree_vertex_set_.push_back(lca_.Query(auxiliary_tree_vertex_set_[i], auxiliary_tree_vertex_set_[i + 1]));
        }
        sort(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end(), [&](int i, int j){
            return et_.get_in(i) < et_.get_in(j);
        });
        auxiliary_tree_vertex_set_.erase(unique(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end()), auxiliary_tree_vertex_set_.end());
        auxiliary_tree_size_ = auxiliary_tree_vertex_set_.size();
    }

    RootedTree<WeightType> Build(){
        RootedTree<WeightType> ret(auxiliary_tree_size_);
        stack<Vertex> st, idx;
        st.push(auxiliary_tree_vertex_set_.front());
        idx.push(0);
        for(int i = 1; i < auxiliary_tree_size_; ++i){
            while(et_.get_out(st.top()) < et_.get_in(auxiliary_tree_vertex_set_[i])) st.pop(), idx.pop();
            if(st.size()){
                WeightType cost = edge_cum_[auxiliary_tree_vertex_set_[i]] - edge_cum_[st.top()];
                ret.AddEdge(idx.top(), i, cost);
            }
            st.push(auxiliary_tree_vertex_set_[i]);
            idx.push(i);
        }
        return ret;
    }

    template<typename Type>
    vector<Type> ConvertData(const vector<Type> &data) const {
        vector<Type> ret(auxiliary_tree_size_);
        for(int i = 0; i < auxiliary_tree_size_; ++i){
            ret[i] = data[auxiliary_tree_vertex_set_[i]];
        }
        return ret;
    }

    private:
    RootedTree<WeightType> &T;
    LowestCommonAncestor<WeightType> lca_;
    EulerTour<WeightType> et_;
    vector<WeightType> edge_cum_;

    vector<Vertex> auxiliary_tree_vertex_set_;
    size_t auxiliary_tree_size_;
    vector<Vertex> convert_to_;
};

#line 2 "Library/Tree/Tree.hpp"

#line 2 "Library/Graph/Graph.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename WeightType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, WeightType weight_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(weight_), idx(idx_){}
    
    bool operator<(const Edge<WeightType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    WeightType cost;
    int idx;
};

template<typename WeightType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int V) : edge_size_(0), adjacent_list_(V){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<WeightType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, WeightType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<WeightType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return adjacent_list_.size();
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<WeightType>> &operator[](const Vertex v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<WeightType>> &operator[](const Vertex v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t edge_size_;
    vector<vector<Edge<WeightType>>> adjacent_list_;
};

template<typename WeightType = int32_t>
Graph<WeightType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<WeightType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 4 "Library/Tree/Tree.hpp"

template<typename WeightType = int32_t>
Graph<WeightType> InputTree(int V, int padding = -1, bool weighted = false){
    Graph<WeightType> G(V);
    for(int i = 0; i < V - 1; ++i){
        Vertex u, v; WeightType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        G.AddUndirectedEdge(u, v, w);
    }
    return G;
}

template<typename WeightType = int32_t>
Graph<WeightType> InputRootedTreeChild(int V, int padding = -1){
    Graph<WeightType> G(V);
    for(Vertex u = 0; u < V; ++u){
        int k; cin >> k;
        for(int i = 0; i < k; ++i){
            Vertex v; cin >> v, v += padding;
            G.AddUndirectedEdge(u, v);
        }
    }
    return G;
}

template<typename WeightType = int32_t>
Graph<WeightType> InputRootedTreeParent(int V, int padding = -1){
    Graph<WeightType> G(V);
    for(Vertex u = 1; u < V; ++u){
        Vertex v; cin >> v, v += padding;
        G.AddUndirectedEdge(u, v);
    }
    return G;
}

template<typename WeightType = int32_t>
vector<vector<Vertex>> RootedTreeAdjacentList(const Graph<WeightType> &T, const Vertex r = 0){
    int V = T.VertexSize();
    vector<vector<Vertex>> ret(V);
    auto rec = [&](auto &self, Vertex u, Vertex p) -> void {
        for(Vertex v : T[u]){
            if(v == p) continue;
            ret[u].push_back(v);
            self(self, v, u);
        }
    };
    rec(rec, r, -1);
    return ret;
}

template<typename WeightType>
vector<Vertex> CalculateTreeParent(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<Vertex> ret(V, -1);
    auto rec = [&](auto &self, Vertex u) -> void {
        for(Vertex v : T[u]){
            if(v == ret[u]) continue;
            ret[v] = u;
            self(self, v);
        }
    };
    rec(rec, r);
    return ret;
}

template<typename WeightType>
vector<WeightType> CalculateTreeCost(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<WeightType> ret(V);
    auto rec = [&](auto &self, Vertex u, Vertex p) -> void {
        for(const Edge<WeightType> &e : T[u]){
            Vertex v = e.to;
            if(v == p) continue;
            ret[v] = e.cost;
            self(self, v, u);
        }
    };
    rec(rec, r, -1);
    return ret;
}

template<typename WeightType>
vector<int> CalculateTreeDepth(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<int> ret(V, 0);
    auto rec = [&](auto &self, Vertex u, Vertex p, int d) -> void {
        ret[u] = d;
        for(Vertex v : T[u]){
            if(v == p) continue;
            self(self, v, u, d + 1);
        }
    };
    rec(rec, r, -1, 0);
    return ret;
}

template<typename WeightType>
vector<WeightType> CalculateTreeDistance(Graph<WeightType> &T, Vertex r = 0){
    int V = T.VertexSize();
    vector<WeightType> ret(V, WeightType(INF));
    auto rec = [&](auto &self, Vertex u) -> void {
        for(const Edge<WeightType> &e : T[u]){
            if(ret[e.to] > ret[u] + e.cost){
                ret[e.to] = ret[u] + e.cost;
                self(self, e.to);
            }
        }
    };
    ret[r] = 0;
    rec(rec, r);
    return ret;
}

template<typename WeightType>
vector<int> CalculateSubtreeSize(Graph<WeightType> &tree, Vertex r = 0){
    int V = tree.VertexSize();
    vector<int> ret(V, 1);
    auto rec = [&](auto self, Vertex u, Vertex p) -> int {
        for(const int v : tree[u]){
            if(v == p) continue;
            ret[u] += self(self, v, u);
        }
        return ret[u];
    };
    rec(rec, r, -1);
    return ret;
}
#line 2 "Library/unauthenticated/EulerTour.hpp"

#line 5 "Library/unauthenticated/EulerTour.hpp"

template<typename WeightType>
class EulerTour{
    public:
    using F = function<WeightType(CostType)>;

    EulerTour(){}

    EulerTour(RootedTree<WeightType> &T, bool one_index = false) :
            T(T),
            vertex_size_(T.get_vertex_size()),
            in_time_(T.get_vertex_size()),
            out_time_(T.get_vertex_size()),
            one_index_(one_index){
        dfs(T.get_root());
    }

    int GetIn(const Vertex v) const {
        return in_time_.at(v - one_index_);
    }

    int GetOut(const Vertex v) const {
        return out_time_.at(v - one_index_);
    }

    pair<int, int> GetPair(const Vertex v) const {
        return make_pair(in_time_.at(v - one_index_), out_time_.at(v - one_index_));
    }

    template<typename Type>
    vector<Type> ConvertVector(const vector<Type> &value, const F in_converter, const F out_converter){
        vector<Type> ret(2 * vertex_size_);
        for(int i = 0; i < vertex_size_; ++i){
            int in_idx = in_time_.at(i), out_idx = out_time_.at(i);
            ret[in_idx] = in_converter(value.at(i));
            ret[out_idx] = out_converter(value.at(i));
        }
        return ret;
    }

    private:
    int time_{0}, one_index_, vertex_size_;

    RootedTree<WeightType> &T;
    vector<int> in_time_, out_time_;

    void dfs(Vertex v){
        in_time_[v] = time_++;
        for(Vertex c : T.get_child(v)){
            dfs(c);
        }
        out_time_[v] = time_++;
    }
};
#line 2 "Library/Tree/LowestCommonAncestor.hpp"

#line 4 "Library/Tree/LowestCommonAncestor.hpp"

template<typename WeightType>
struct LowestCommonAncestor{
    public:
    LowestCommonAncestor(Graph<WeightType> &tree) : T(tree), depth_(CalculateTreeDepth(tree)){
        int V = T.VertexSize();
        height_ = 1;
        while((1 << height_) < V) ++height_;
        auto par = CalculateTreeParent(T);
        parent_.resize(height_, vector<Vertex>(V, -1));
        for(Vertex i = 0; i < V; ++i){
            parent_[0][i] = par[i];
        }
        for(int k = 0; k + 1 < height_; ++k){
            for(Vertex i = 0; i < V; ++i){
                if(parent_[k][i] < 0) parent_[k + 1][i] = -1;
                else parent_[k + 1][i] = parent_[k][parent_[k][i]];
            }
        }
    }

    Vertex Query(Vertex u, Vertex v){
        if(depth_[u] < depth_[v]) swap(u, v);
        for(int k = 0; k < height_; ++k){
            if((depth_[u] - depth_[v]) >> k & 1){
                u = parent_[k][u];
            }
        }
        if(u == v) return u;
        for(int k = height_ - 1; k >= 0; --k){
            if(parent_[k][u] != parent_[k][v]){
                u = parent_[k][u];
                v = parent_[k][v];
            }
        }
        return parent_[0][u];
    }

    private:
    Graph<WeightType> &T;
    int height_;
    vector<int> depth_;
    vector<vector<Vertex>> parent_;
};
#line 4 "Library/unauthenticated/AuxiliaryTree.hpp"

template<typename WeightType>
class AuxiliaryTree{
    public:
    AuxiliaryTree(RootedTree<WeightType> &tree) :
            T(tree), lca_(tree), et_(tree), edge_cum_(CalculateTreeCumlativeSum(tree)){
    }

    void Set(const vector<Vertex> &vertex_set){
        auxiliary_tree_vertex_set_ = vertex_set;
        auxiliary_tree_size_ = auxiliary_tree_vertex_set_.size();
        sort(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end(), [&](int i, int j){
            return et_.get_in(i) < et_.get_in(j);
        });
        for(int i = 0; i < auxiliary_tree_size_ - 1; ++i){
            auxiliary_tree_vertex_set_.push_back(lca_.Query(auxiliary_tree_vertex_set_[i], auxiliary_tree_vertex_set_[i + 1]));
        }
        sort(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end(), [&](int i, int j){
            return et_.get_in(i) < et_.get_in(j);
        });
        auxiliary_tree_vertex_set_.erase(unique(auxiliary_tree_vertex_set_.begin(), auxiliary_tree_vertex_set_.end()), auxiliary_tree_vertex_set_.end());
        auxiliary_tree_size_ = auxiliary_tree_vertex_set_.size();
    }

    RootedTree<WeightType> Build(){
        RootedTree<WeightType> ret(auxiliary_tree_size_);
        stack<Vertex> st, idx;
        st.push(auxiliary_tree_vertex_set_.front());
        idx.push(0);
        for(int i = 1; i < auxiliary_tree_size_; ++i){
            while(et_.get_out(st.top()) < et_.get_in(auxiliary_tree_vertex_set_[i])) st.pop(), idx.pop();
            if(st.size()){
                WeightType cost = edge_cum_[auxiliary_tree_vertex_set_[i]] - edge_cum_[st.top()];
                ret.AddEdge(idx.top(), i, cost);
            }
            st.push(auxiliary_tree_vertex_set_[i]);
            idx.push(i);
        }
        return ret;
    }

    template<typename Type>
    vector<Type> ConvertData(const vector<Type> &data) const {
        vector<Type> ret(auxiliary_tree_size_);
        for(int i = 0; i < auxiliary_tree_size_; ++i){
            ret[i] = data[auxiliary_tree_vertex_set_[i]];
        }
        return ret;
    }

    private:
    RootedTree<WeightType> &T;
    LowestCommonAncestor<WeightType> lca_;
    EulerTour<WeightType> et_;
    vector<WeightType> edge_cum_;

    vector<Vertex> auxiliary_tree_vertex_set_;
    size_t auxiliary_tree_size_;
    vector<Vertex> convert_to_;
};

Back to top page