#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using pi = pair<int, int>;
const int MAXN = (int)(7e4) + 5;
vector<int> adj[MAXN];
int par[MAXN];
set<int> minc[MAXN];
set<int> maxc[MAXN];
int ans[MAXN];
vector<int> color[MAXN];
vector<int> to[MAXN];
bool visited[MAXN];
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);
}
}
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()
{
int N;
cin >> N;
FR(i, N-1) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
int K;
cin >> K;
FR(i, K) {
char c;
int x, y, z;
cin >> c;
cin >> x >> y >> z;
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) {
int j = *unvis.begin();
unvis.erase(j);
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) {
deq.push(e);
}
}
break;
}
}
}
}
for (int i = 1; i < N; i++) {
cout << par[i]+1 << " " << i+1 << " " << ans[i] << '\n';
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 0; i < condense.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
433 ms |
61072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
23276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
