| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 343426 | ijxjdjd | Min-max tree (BOI18_minmaxtree) | C++14 | 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.
int deg[MAXN];
unordered_map<int, int> condense;
int rev[MAXN];
pi merge(pi x, pi y) {
if (minc[x.first].size() < minc[y.first].size()) {
swap(x.first, y.first);
}
if (maxc[x.second].size() < minc[y.second].size()) {
swap(x.second, y.second);
}
for (int i : minc[y.first]) {
if (minc[x.first].count(i)) {
minc[x.first].erase(i);
}
else {
minc[x.first].insert(i);
}
}
for (int i : maxc[y.second]) {
if (maxc[x.second].count(i)) {
maxc[x.second].erase(i);
}
else {
maxc[x.second].insert(i);
}
}
maxc[x.second].erase(i);
return x;
}
pi root(int n, int p) {
pi cur = {n, n};
par[n] = p;
for (int e : adj[n]) {
if (e != p) {
cur = merge(cur, root(e, n));
}
}
if (minc[cur.first].size() > 0) {
int z = *(minc[cur.first].rbegin());
if (!condense.count(z)) {
rev[condense.size()] = z;
condense[z] = condense.size();
}
color[condense[z]].push_back(n);
to[n].push_back(condense[z]);
}
if (maxc[cur.second].size() > 0) {
int z = *(maxc[cur.second].begin());
if (!condense.count(z)) {
rev[condense.size()] = z;
condense[z] = condense.size();
}
color[condense[z]].push_back(n);
to[n].push_back(condense[z]);
}
return cur;
}
int main()
{
// freopen("input.in", "r", stdin);
int N;
cin >> N;
FR(i, N-1) {
int a, b;
cin >> a >> b;
a--; b--;
ans[i] = -1;
adj[a].push_back(b);
adj[b].push_back(a);
}
ans[N-1] = -1;
int K;
cin >> K;
FR(i, K) {
char c;
int x, y, z;
cin >> c;
cin >> x >> y >> z;
x--, y--;
if (x != y) {
if (c == 'm') {
minc[x].insert(z);
minc[y].insert(z);
}
else {
maxc[x].insert(z);
maxc[y].insert(z);
}
}
}
root(0, 0);
queue<int> deq;
unordered_set<int> unvis;
for (int i = 0; i < condense.size(); i++) {
deg[i] = color[i].size();
if (deg[i] == 1) {
deq.push(i);
}
else {
unvis.insert(i);
}
}
while (unvis.size() > 0) {
while (deq.size() > 0) {
int next = deq.front(); deq.pop();
for (int j : color[next]) {
if (!visited[j]) {
visited[j] = true;
ans[j] = rev[next];
for (int e : to[j]) {
deg[e]--;
if (deg[e] == 1 && unvis.count(e)) {
deq.push(e);
unvis.erase(e);
}
}
break;
}
}
}
if (unvis.size() > 0) {
int j = *unvis.begin();
unvis.erase(j);
deq.push(j);
}
}
for (int i = 1; i < N; i++) {
if (ans[i] == -1) {
if (to[i].size() > 0) {
ans[i] = rev[to[i][0]];
}
else {
ans[i] = 1;
}
}
cout << par[i]+1 << " " << i+1 << " " << ans[i] << '\n';
}
return 0;
}