Cod sursa(job #2501056)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 29 noiembrie 2019 00:57:34
Problema Heavy Path Decomposition Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 11.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
 
namespace segment_tree {
 
template <typename Tinfo>
class DefaultCombiner {
 public:
    Tinfo operator()(Tinfo const &lsh, Tinfo const &rsh) {
        return std::max(lsh, rsh);
    }
};
 
template <typename Tinfo, typename Combiner = DefaultCombiner<Tinfo> >
class SegmentTree {
 private:
 public:
    int size_;
    std::vector<Tinfo> tree_;
 
    /*
     * Function that compute an aggregate, such as max/min/sum,
     * of the interval [lsh, rsh].
     */
    Combiner combine_;
 
 public:
    // Default Constructor
    SegmentTree();
 
    // Constructor
    SegmentTree(std::vector<Tinfo> array);
 
    // Destructor
    ~SegmentTree();
 
    /*
     * Build a segment tree from array.
     *
     * @param array // given array to build.
     */
    void build(std::vector<Tinfo> array);
 
    /**
     * Update value of element from position p.
     * 
     * @param p, value // Set value at position p.
     */
    void update(int p, int value);
 
    /**
     * Get an aggregate on interval [lsh, rsh).
     * 
     * @param lsh, rsh // left and right bounds of the interval.
     * @return an aggregate on interval [lsh, rsh).
     */
    Tinfo query(int lsh, int rsh);
 
    /*
     * Get size of array used.
     *
     * @return size of array used.
     */
    int size();
};
 
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::SegmentTree(): size_(0) {}
 
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::SegmentTree(std::vector<Tinfo> array): size_(array.size()), tree_(2 * array.size()) {
    for (int i = 0; i < size_; ++i) {
        tree_[size_ + i] = array[i];
    }
 
    for (int i = size_ - 1; i > 0; --i) {
        tree_[i] = combine_(tree_[i << 1], tree_[ i<< 1 | 1]);
    }
}
 
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::~SegmentTree() {}
 
template <typename Tinfo, typename Combiner>
void SegmentTree<Tinfo, Combiner>::build(std::vector<Tinfo> array) {
    size_ = array.size();
    tree_.resize(2 * size_);
 
    for (int i = 0; i < size_; ++i) {
        tree_[size_ + i] = array[i];
    }
 
    for (int i = size_ - 1; i > 0; --i) {
        tree_[i] = combine_(tree_[i << 1], tree_[ i<< 1 | 1]);
    }
}
 
template <typename Tinfo, typename Combiner>
void SegmentTree<Tinfo, Combiner>::update(int p, int value) {
    for (tree_[p += size_] = value, p >>= 1; p > 0; p >>= 1) {
        tree_[p] = combine_(tree_[p << 1], tree_[p << 1 | 1]);
    }
}
 
template <typename Tinfo, typename Combiner>
Tinfo SegmentTree<Tinfo, Combiner>::query(int lsh, int rsh) {
    bool used_lsh = false, used_rsh = false;
    Tinfo ret_lsh, ret_rsh;
 
    for (lsh += size_, rsh += size_; lsh < rsh; lsh >>= 1, rsh >>= 1) {
        if (lsh & 1) {
            if (used_lsh) {
                ret_lsh = combine_(ret_lsh, tree_[lsh++]);
            } else {
                ret_lsh = tree_[lsh++];
                used_lsh = true;
            }
        }
 
        if (rsh & 1) {
            if (used_rsh) {
                ret_rsh = combine_(tree_[--rsh], ret_rsh);
            } else {
                ret_rsh = tree_[--rsh];
                used_rsh = true;
            }
        }
    }
 
    if (used_lsh && used_rsh) {
        return combine_(ret_lsh, ret_rsh);
    } else {
        return (used_lsh)? ret_lsh: ret_rsh;
    }
}
 
template <typename Tinfo, typename Combiner>
int SegmentTree<Tinfo, Combiner>::size() {
    return size_;
}
 
} // namespace segment_tree
 
namespace tree_decomposition {
 
template <typename Tinfo>
class DefaultCombiner {
 public:
    Tinfo operator()(Tinfo const &lsh, Tinfo const &rsh) {
        return std::max(lsh, rsh);
    }
};
 
template <typename Tinfo, typename Combiner = DefaultCombiner<Tinfo> >
class TreeDecomposition {
 private:
 public:
    struct Node {
        std::vector<int> neighbors_;
    };
 
    struct Path {
        segment_tree::SegmentTree<Tinfo, Combiner> segment_tree_;
        std::vector<int> array_; // array of nodes from path
        int parent_; // parent node
    };
 
    int size_;
    /*
     * Function that compute an aggregate, such as max/min/sum,
     * of the interval [lsh, rsh].
     */
    Combiner combine_;
    std::vector<Path> path_;         // the tree is decomposed into paths
    std::vector<Node> node_;         // each node has a list of neighbours
    std::vector<Tinfo> info_;        // information of each node
    std::vector<int> depth_;         // depth of each node
    std::vector<int> what_path_;     // path of each node
    std::vector<int> what_position_; // position in path of each node
 
    /**
     * Depth-first search for paths build.
     * 
     * @param node - Current node in search.
     * @return subtree weight of current node.
     */
    int dfs(int node);
 
 public:
    // Constructor
    TreeDecomposition(int size);
 
    // Destructor
    ~TreeDecomposition();
 
    /**
     * Access information associated to existing node.
     * 
     * @param node Node of whose information will be returned.
     * @return reference to information associated to the given node.
     */
    Tinfo& operator[](int node);
 
    /**
     * Adds an edge between two existing nodes.
     *
     * @param src Source node of the edge to be added.
     * @param dst Destination node of the edge to be added.
     */
    void add_edge(int src, int dst);
 
    /**
     * Gets the tree size.
     *
     * @return Number of nodes in the tree.
     */
    int size();
 
    /**
     * Build tree decomposition.
     */
    void build();
 
    /**
     * Update value of node.
     * 
     * @param node, value // Set value of node.
     */
    void update(int node, Tinfo value);
 
    /**
     * Returns an aggregate, such as max/min/sum,
     * of the weights of the nodes or edges on the path
     * from node src to node dst.
     * 
     * @param src Source node.
     * @param dst Destination node.
     * @return max/min/sum of the weights of the nodes or
     * edges on the path from node src to node dst.
     */
    Tinfo query(int src, int dst);
};
 
template <typename Tinfo, typename Combiner>
int TreeDecomposition<Tinfo, Combiner>::dfs(int node) {
    bool leaf_node = true;
    int weight = 1, max_weight = 0, chosen_son, son_weight;
 
    for (auto son: node_[node].neighbors_) {
        if (!depth_[son]) { // unvisited son
            leaf_node = false;
 
            depth_[son] = depth_[node] + 1;
            son_weight = dfs(son);
 
            weight += son_weight;
            path_[what_path_[son]].parent_ = node; // the parent of the paths of sons is node
 
            if (max_weight < son_weight) {
                max_weight = son_weight;
                chosen_son = son;
            }
        }
    }
 
    if (leaf_node) { // create a new path in the leaves
        Path* new_path = new Path();
        path_.push_back(*new_path);
        path_[path_.size() - 1].array_.push_back(node);
        what_path_[node] = path_.size() - 1;
        what_position_[node] = path_[path_.size() - 1].array_.size() - 1;
    } else {
        path_[what_path_[chosen_son]].array_.push_back(node);
        what_path_[node] = what_path_[chosen_son];
        what_position_[node] = path_[what_path_[chosen_son]].array_.size() - 1;
    }
 
    return weight;
}
 
template <typename Tinfo, typename Combiner>
TreeDecomposition<Tinfo, Combiner>::TreeDecomposition(int size): size_(size), node_(size),
    info_(size), depth_(size, 0), what_path_(size), what_position_(size) {}
 
template <typename Tinfo, typename Combiner>
TreeDecomposition<Tinfo, Combiner>::~TreeDecomposition() {}
 
template <typename Tinfo, typename Combiner>
Tinfo& TreeDecomposition<Tinfo, Combiner>::operator[](int node) {
    return info_[node];
}
 
template <typename Tinfo, typename Combiner>
void TreeDecomposition<Tinfo, Combiner>::add_edge(int src, int dst) {
    node_[src].neighbors_.push_back(dst);
    node_[dst].neighbors_.push_back(src);
}
 
template <typename Tinfo, typename Combiner>
int TreeDecomposition<Tinfo, Combiner>::size() {
    return size_;
}
 
template <typename Tinfo, typename Combiner>
void TreeDecomposition<Tinfo, Combiner>::build() {
    depth_[0] = 1;
    dfs(0);
    path_[what_path_[0]].parent_ = -1;
 
    // create segment tree for each path
    for (auto it_path = path_.begin(); it_path != path_.end(); it_path++) {
        std::vector<Tinfo> tmp_info;
        for (auto path_node: (*it_path).array_) {
            tmp_info.push_back(info_[path_node]);
        }
 
        (*it_path).segment_tree_.build(tmp_info);
    }
}
 
template <typename Tinfo, typename Combiner>
void TreeDecomposition<Tinfo, Combiner>::update(int node, Tinfo value) {
    info_[node] = value;
    path_[what_path_[node]].segment_tree_.update(what_position_[node], value);
}
 
template <typename Tinfo, typename Combiner>
Tinfo TreeDecomposition<Tinfo, Combiner>::query(int src, int dst) {
    bool used_src = false, used_dst = false;
    int parent_src, parent_dst;
    Tinfo ret_src, ret_dst, ret;
 
 
    while (what_path_[src] != what_path_[dst]) {
        parent_src = path_[what_path_[src]].parent_;
        parent_dst = path_[what_path_[dst]].parent_;
 
        if (parent_dst == -1 || (parent_src != -1 && depth_[parent_src] > depth_[parent_dst])) {
            ret = path_[what_path_[src]].segment_tree_.query(what_position_[src], path_[what_path_[src]].array_.size());
 
            if (used_src) {
                ret_src = combine_(ret_src, ret);
            } else {
                ret_src = ret;
                used_src = true;
            }
 
            src = parent_src;
        } else {
            ret = path_[what_path_[dst]].segment_tree_.query(what_position_[dst], path_[what_path_[dst]].array_.size());
 
            if (used_dst) {
                ret_dst = combine_(ret ,ret_dst);
            } else {
                ret_dst = ret;
                used_dst = true;
            }
 
            dst = parent_dst;
        }
    }
 
    if (depth_[src] < depth_[dst]) {
        std::swap(src, dst);
        ret = path_[what_path_[src]].segment_tree_.query(what_position_[src], what_position_[dst] + 1);
    } else {
    	ret = path_[what_path_[src]].segment_tree_.query(what_position_[src], what_position_[dst] + 1);
	}
 
    if (used_src) {
        ret_src = combine_(ret_src, ret);
    } else {
        ret_src = ret;
        used_src = true;
    }
 
    if (used_src && used_dst) {
        return combine_(ret_src, ret_dst);
    } else {
        return (used_src)? ret_src: ret_dst;
    }
}
 
} // namespace tree_decomposition
 
std::ifstream fin("heavypath.in");
std::ofstream fout("heavypath.out");
int main() {
 
    int N, M, val, t, x, y;
    fin >> N >> M;
 
    tree_decomposition::TreeDecomposition<int> treeDecomp(N);
 
    for (int i = 0; i < N; ++i) {
        fin >> treeDecomp[i];
    }
 
    for (int i = 1; i < N; ++i) {
        fin >> x >> y;
        treeDecomp.add_edge(x - 1, y - 1);
    }
 
    treeDecomp.build();
 
    for (int i = 0; i < M; ++i) {
        fin >> t >> x >> y;
 
        if (t) {
            fout << treeDecomp.query(x - 1, y - 1) << '\n';
        } else {
            treeDecomp.update(x - 1, y);
        }
    }
 
    return 0;
}