이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
template <typename T>
class StaticTopTree {
public:
enum Type { Vertex, Compress, Rake, AddEdge, AddVertex };
StaticTopTree(vector<vector<int>> &g, int root = 0) : g_(g), root_(root) {
int n = g_.size();
parent_.resize(4 * n, -1);
left_.resize(4 * n, -1);
right_.resize(4 * n, -1);
vertex_type_.resize(4 * n, Type::Vertex);
paths_.resize(4 * n);
points_.resize(4 * n);
cur_idx_ = n;
build();
}
private:
// do HLD(Heavy Light Decomposition), move heavy edge to g_[c][0];
int dfs(int c) {
int s = 1, best = 0;
for (int &d : g_[c]) {
int t = dfs(d);
s += t;
if (best < t) best = t, swap(d, g_[c][0]);
}
return s;
}
int add(int k, int l, int r, Type t) {
if (k == -1) k = cur_idx_++;
parent_[k] = -1, left_[k] = l, right_[k] = r, vertex_type_[k] = t;
if (l != -1) parent_[l] = k;
if (r != -1) parent_[r] = k;
return k;
}
pair<int, int> merge(const vector<pair<int, int>> &a, Type t) {
if (a.size() == 1) return a[0];
int u = 0;
for (auto &[_, s] : a) u += s;
vector<pair<int, int>> b, c;
// make sure b/c at least has 1 item
for (auto& [i, s] : a) (u > s ? b : c).emplace_back(i, s), u -= s * 2;
// if use (u > 0 ? b : c), c may be 0 size, will be RE
// for (auto &[i, s] : a) (u > 0 ? b : c).emplace_back(i, s), u -= s * 2;
auto [i, si] = merge(b, t);
auto [j, sj] = merge(c, t);
return {add(-1, i, j, t), si + sj};
}
pair<int, int> compress(int i) {
vector<pair<int, int>> chs{add_vertex(i)};
while (!g_[i].empty()) chs.push_back(add_vertex(i = g_[i][0]));
return merge(chs, Type::Compress);
}
pair<int, int> rake(int i) {
vector<pair<int, int>> chs;
for (int j = 1; j < (int)g_[i].size(); j++)
chs.push_back(add_edge(g_[i][j]));
return chs.empty() ? make_pair(-1, 0) : merge(chs, Type::Rake);
}
pair<int, int> add_edge(int i) {
auto [j, sj] = compress(i);
return {add(-1, j, -1, Type::AddEdge), sj};
}
pair<int, int> add_vertex(int i) {
auto [j, sj] = rake(i);
return {add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), sj + 1};
}
void build() {
dfs(root_);
auto [i, n] = compress(root_);
stt_root_ = i;
}
// private:
public:
// adjacent list of initial tree, chridren are stored in g_[parent],
// parent can not be stored in g_[child] in this implement!!!
// g_ must be a rooted tree
vector<vector<int>> &g_;
int root_; // an index of the root in g
int stt_root_; // an index of the root in static top tree
vector<int> parent_, left_, right_; // parent, left child, right child
vector<Type> vertex_type_; // type of vertices
int cur_idx_; // a variable for the index increment
vector<int> values;
private:
// u: upper boundary vertex, v: lower boundary vertex
struct TP {
// ll fv;
ll c012,c01u,c2,c0,cu12,c01v,cv12,cu1v,c0_u_2,cvu_2,c0_uv;
friend ostream &operator<<(ostream &os, const TP &p) {
return os << "c012:" << p.c012 << "\n"
<< "c01u:" << p.c01u << "\n"
<< "c2:" << p.c2 << "\n"
<< "c0:" << p.c0 << "\n"
<< "cu12:" << p.cu12 << "\n"
<< "c01v:" << p.c01v << "\n"
<< "cv12:" << p.cv12 << "\n"
<< "cu1v:" << p.cu1v << "\n"
<< "c0_u_2:" << p.c0_u_2 << "\n"
<< "cvu_2:" << p.cvu_2 << "\n"
<< "c0_uv:" << p.c0_uv << "\n";
}
};
using Point = TP;
using Path = TP;
vector<Point> points_;
vector<Path> paths_;
Path vertex(int i) {
TP tp;
// tp.fv= values[i];
tp.c012 = 0;
tp.c01u = 0;
tp.c2 = (values[i] == 2);
tp.c0 = (values[i] == 0);
tp.cu12 = 0;
tp.c01v = 0;
tp.cv12 = 0;
tp.cu1v = (values[i] == 1);
tp.c0_u_2 = 0;
tp.cvu_2 = 0;
tp.c0_uv = 0;
return tp;
}
Path compress(Path p, Path c) {
TP tp;
// tp.fv = c.fv;
tp.c012 = p.c012 + c.c012 + p.c01v * c.c2 + p.cv12 * c.c0 + p.c0 * c.cu12 + p.c2 * c.c01u;
tp.c01u = p.c01u + c.c01u + p.cu1v * c.c0;
tp.c2 = p.c2 + c.c2;
tp.c0 = p.c0 + c.c0;
tp.cu12 = p.cu12 + c.cu12 + p.cu1v * c.c2;
tp.c01v = p.c01v + c.c01v + p.c0 * c.cu1v;
tp.cv12 = p.cv12 + c.cv12 + p.c2 * c.cu1v;
tp.cu1v = p.cu1v + c.cu1v;
tp.c0_u_2 = p.c0_u_2 + c.c0 * p.cvu_2 + c.c2 * p.c0_uv;
tp.cvu_2 = p.cvu_2;
tp.c0_uv = p.c0_uv;
return tp;
}
Path add_vertex(Point p, int i) {
TP tp;
// tp.fv = values[i];
tp.c012 = p.c012 + p.cu12 * (values[i] == 0) + p.c01u * (values[i] == 2) + p.c0_u_2 * (values[i] == 1);
tp.c01u = p.c01u + p.c0 * (values[i] == 1);
tp.c2 = p.c2 + (values[i] == 2);
tp.c0 = p.c0 + (values[i] == 0);
tp.cu12 = p.cu12 + (values[i] == 1) * p.c2;
tp.c01v = p.c01u + (values[i] == 1) * p.c0;
tp.cv12 = p.cu12 + (values[i] == 1) * p.c2;
tp.cu1v = (values[i] == 1);
tp.c0_u_2 = p.c0_u_2;
tp.cvu_2 = p.c2;
tp.c0_uv = p.c0;
return tp;
}
Point add_edge(Path p) {
return p;
}
Point rake(Point p, Point c) {
TP tp;
// tp.fv = values[i];
tp.c012 = p.c012 + c.c012;
tp.c01u = p.c01u + c.c01u;
tp.c2 = p.c2 + c.c2;
tp.c0 = p.c0 + c.c0;
tp.cu12 = p.cu12 + c.cu12;
tp.c01v = p.c01v + c.c01v;
tp.cv12 = p.cv12 + c.cv12;
tp.cu1v = 0;
tp.c0_u_2 = p.c0 * c.c2 + p.c2 * c.c0;
// tp.cvu_2 = 0;
// tp.c0_uv = 0;
return tp;
}
void update_node(int k) {
if (vertex_type_[k] == Vertex) paths_[k] = vertex(k);
else if (vertex_type_[k] == Compress) paths_[k] = compress(paths_[left_[k]], paths_[right_[k]]);
else if (vertex_type_[k] == AddVertex) paths_[k] = add_vertex(points_[left_[k]], k);
else if (vertex_type_[k] == AddEdge) points_[k] = add_edge(paths_[left_[k]]);
else if (vertex_type_[k] == Rake) points_[k] = rake(points_[left_[k]], points_[right_[k]]);
}
void init(int k) {
if (left_[k] != -1) init(left_[k]);
if (right_[k] != -1) init(right_[k]);
update_node(k);
dbg(mp(k, vertex_type_[k]));
dbg(points_[k]);
dbg(paths_[k]);
}
public:
void update_tree(int k, T v) {
values[k] = v;
while (k != -1) {
update_node(k);
k = parent_[k];
}
}
void init() {
init(stt_root_);
}
T get_answer() {
return paths_[stt_root_].c012;
}
};
unique_ptr<StaticTopTree<ll>> p_stt = nullptr;
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
vector<vi> edges(N);
rep(i,0,N-1) {
edges[U[i]].emplace_back(V[i]);
edges[V[i]].emplace_back(U[i]);
}
vector<vi> g(N);
function<void(int,int)> dfs=[&] (int u, int p) {
for(int v : edges[u]) {
if (v != p) {
g[u].emplace_back(v);
dfs(v, u);
}
}
};
dfs(0, -1);
dbg(g);
p_stt = make_unique<StaticTopTree<ll>>(g);
p_stt->values = F;
dbg(p_stt->values);
p_stt->init();
}
void change(int X, int Y) {
p_stt->update_tree(X, Y);
}
long long num_tours() {
return p_stt->get_answer();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |