| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 860807 | green_gold_dog | Unique Cities (JOI19_ho_t5) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(0);
mt19937_64 rnd64(0);
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
struct node {
pair<ll, ll> x;
ll y;
ll sz;
node *l, *r;
node(pair<ll, ll> x = pair<ll, ll>(0, 0), node *l = nullptr, node *r = nullptr): x(x), l(l), r(r) {
y = rnd32();
sz = 1;
}
};
ll get(node *t) {
if (t == nullptr) {
return 0;
}
return t->sz;
}
void upd(node *t) {
t->sz = get(t->l) + get(t->r) + 1;
}
pair<node*, node*> split(node *t, pair<ll, ll> x) {
if (t == nullptr) {
return make_pair(nullptr, nullptr);
}
if (t->x > x) {
auto[l, r] = split(t->l, x);
t->l = r;
upd(t);
return make_pair(l, t);
} else {
auto[l, r] = split(t->r, x);
t->r = l;
upd(t);
return make_pair(t, r);
}
}
node* merge(node *l, node *r) {
if (l == nullptr) {
return r;
}
if (r == nullptr) {
return l;
}
if (l->y > r->y) {
l->r = merge(l->r, r);
upd(l);
return l;
} else {
r->l = merge(l, r->l);
upd(r);
return r;
}
}
struct cartesian_tree {
node* root;
vector<vector<pair<ll, node*>>> b;
vector<ll> ad;
vector<ll> last;
ll a = 0;
cartesian_tree(ll c) {
last.resize(c, 0);
ad.push_back(0);
root = nullptr;
b.push_back(vector<pair<ll, node*>>(0));
}
void add() {
a++;
ad.back()++;
}
void make() {
b.push_back(vector<pair<ll, node*>>(0));
ad.push_back(0);
}
void back() {
a -= ad.back();
ad.pop_back();
reverse(b.back().begin(), b.back().end());
for (auto[bb, t] : b.back()) {
if (bb == 1) {
root = merge(t, root);
} else {
pair<ll, ll> x = t->x;
last[x.second] = bb;
auto[l, r] = split(root, x);
x.second--;
auto[l_l, l_r] = split(l, x);
root = merge(l_l, r);
}
}
b.pop_back();
}
ll getsz() {
return get(root);
}
void del(ll x) {
x -= a;
auto[l, r] = split(root, make_pair(x, INF32));
b.back().emplace_back(1, l);
root = r;
}
void insert(ll c) {
auto[l, r] = split(root, make_pair(last[c], c));
auto[l_l, l_r] = split(l, make_pair(last[c], c - 1));
if (get(l_r) == 0) {
l_r = new node(make_pair(-a, c));
b.back().emplace_back(last[c], l_r);
last[c] = -a;
root = merge(l_l, r);
auto[nl, nr] = split(root, l_r->x);
l_l = nl;
r = nr;
}
root = merge(merge(l_l, l_r), r);
}
};
ll get_md(vector<vector<ll>>& tree, ll v) {
vector<ll> dist(tree.size(), INF32);
queue<ll> q;
dist[v] = 0;
q.push(v);
ll lst = v;
while (!q.empty()) {
ll x = q.front();
q.pop();
lst = x;
for (auto i : tree[x]) {
if (assign_min(dist[i], dist[x] + 1)) {
q.push(i);
}
}
}
return lst;
}
bool find(ll v, ll p, vector<vector<ll>>& tree, ll x, vector<ll>& now) {
now.push_back(v);
if (v == x) {
return true;
}
for (auto i : tree[v]) {
if (i != p) {
if (find(i, v, tree, x, now)) {
return true;
}
}
}
now.pop_back();
return false;
}
void dfs(ll v, vector<bool>& used, vector<vector<ll>>& tree, vector<ll>& h) {
h[v] = 0;
used[v] = true;
for (auto i : tree[v]) {
if (!used[i]) {
dfs(i, used, tree, h);
assign_max(h[v], h[i]);
}
}
h[v]++;
}
void dfs2(ll v, ll p, vector<vector<ll>>& tree, vector<ll>& h, cartesian_tree& ct, vector<ll>& ans, vector<ll>& c) {
vector<pair<ll, ll>> all;
for (auto i : tree[v]) {
if (i != p) {
all.emplace_back(h[i], i);
}
}
sort(all.begin(), all.end());
ct.make();
if (all.size() > 1) {
ct.del(all[1].first);
}
ct.insert(c[v]);
ct.add();
if (!all.empty()) {
dfs2(all[0].second, v, tree, h, ct, ans, c);
}
ct.back();
ct.make();
if (!all.empty()) {
ct.del(all[0].first);
}
ans[v] = ct.getsz();
ct.insert(c[v]);
ct.add();
if (!all.empty()) {
all.erase(all.begin());
}
for (auto[_, i] : all) {
dfs2(i, v, tree, h, ct, ans, c);
}
ct.back();
}
void solve() {
ll n, m;
cin >> n >> m;
vector<vector<ll>> tree(n);
for (ll i = 1; i < n; i++) {
ll a, b;
cin >> a >> b;
a--;
b--;
tree[a].push_back(b);
tree[b].push_back(a);
}
ll l = get_md(tree, 0);
ll r = get_md(tree, l);
vector<ll> way;
find(l, l, tree, r, way);
vector<ll> c(n);
for (ll i = 0; i < n; i++) {
cin >> c[i];
c[i]--;
}
vector<ll> ans(n, -1);
vector<bool> used(n, false);
for (auto i : way) {
used[i] = true;
}
vector<ll> h(n, 0);
for (auto i : way) {
dfs(i, used, tree, h);
}
for (ll i = 0; i < n; i++) {
used[i] = false;
}
for (auto i : way) {
used[i] = true;
}
ll mid = way[way.size() / 2];
bool b = false;
cartesian_tree ct(m);
for (ll i = 0; i < way.size(); i++) {
if (way[i] == mid) {
b = true;
}
if (b) {
ct.make();
ct.del(way.size() - i - 1);
ans[way[i]] = ct.getsz();
ct.insert(c[way[i]]);
ct.add();
for (auto j : tree[way[i]]) {
if (!used[j]) {
dfs2(j, way[i], tree, h, ct, ans, c);
}
}
ct.back();
}
ct.del(h[way[i]] - 1);
ct.insert(c[way[i]]);
ct.add();
}
ct = cartesian_tree(m);
mid = way[way.size() / 2 - 1];
reverse(way.begin(), way.end());
b = false;
for (ll i = 0; i < way.size(); i++) {
if (way[i] == mid) {
b = true;
}
if (b) {
ct.make();
ct.del(way.size() - i - 1);
ans[way[i]] = ct.getsz();
ct.insert(c[way[i]]);
ct.add();
for (auto j : tree[way[i]]) {
if (!used[j]) {
dfs2(j, way[i], tree, h, ct, ans, c);
}
}
ct.back();
}
ct.del(h[way[i]] - 1);
ct.insert(c[way[i]]);
ct.add();
}
for (auto i : ans) {
cout << i << '\n';
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}