#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p;
const int inf = 1e9 + 7;
struct Query {
int s, e, x, mx;
};
//Input / HLD - var
int in[70707], dep[70707], par[70707], top[70707], sz[70707];
vector<int> g[70707], inp[70707];
int chk[70707], pv, n, q;
vector<Query> qry;
//Get Answer - var
map<int, int> mp;
int cnt[70707], ans[70707];
int vis[70707];
vector<int> track[70707];
//Segment Tree - var
int treemin[1 << 18], treemax[1 << 18];
int tmpmin[1 << 18], tmpmax[1 << 18];
int mn[70707], mx[70707];
//Segment Tree - function
void pushmin(int node, int s, int e) {
if (tmpmin[node] == inf) return;
treemin[node] = min(treemin[node], tmpmin[node]);
if (s ^ e) {
tmpmin[node * 2] = min(tmpmin[node], tmpmin[node * 2]);
tmpmin[node * 2 + 1] = min(tmpmin[node], tmpmin[node * 2 + 1]);
}
tmpmin[node] = inf;
}
void pushmax(int node, int s, int e) {
if (tmpmax[node] == -inf) return;
treemax[node] = max(treemax[node], tmpmax[node]);
if (s ^ e) {
tmpmax[node * 2] = max(tmpmax[node], tmpmax[node * 2]);
tmpmax[node * 2 + 1] = max(tmpmax[node], tmpmax[node * 2 + 1]);
}
tmpmax[node] = -inf;
}
void updatemin(int node, int s, int e, int l, int r, int v) {
pushmin(node, s, e);
if (r < s || e < l) return;
if (l <= s && e <= r) {
treemin[node] = min(treemin[node], v);
if (s ^ e) {
tmpmin[node * 2] = min(tmpmin[node * 2], v);
tmpmin[node * 2 + 1] = min(tmpmin[node * 2 + 1], v);
}
return;
}
int m = s + e >> 1;
updatemin(node * 2, s, m, l, r, v);
updatemin(node * 2 + 1, m + 1, e, l, r, v);
treemin[node] = min(treemin[node * 2], treemin[node * 2 + 1]);
}
void updatemax(int node, int s, int e, int l, int r, int v) {
pushmax(node, s, e);
if (r < s || e < l) return;
if (l <= s && e <= r) {
treemax[node] = max(treemax[node], v);
if (s ^ e) {
tmpmax[node * 2] = max(tmpmax[node * 2], v);
tmpmax[node * 2 + 1] = max(tmpmax[node * 2 + 1], v);
}
return;
}
int m = s + e >> 1;
updatemax(node * 2, s, m, l, r, v);
updatemax(node * 2 + 1, m + 1, e, l, r, v);
treemax[node] = max(treemax[node * 2], treemax[node * 2 + 1]);
}
int querymin(int node, int s, int e, int l, int r) {
pushmin(node, s, e);
if (r < s || e < l) return inf;
if (l <= s && e <= r) return treemin[node];
int m = s + e >> 1;
int t1 = querymin(node * 2, s, m, l, r);
int t2 = querymin(node * 2 + 1, m + 1, e, l, r);
return min(t1, t2);
}
int querymax(int node, int s, int e, int l, int r) {
pushmax(node, s, e);
if (r < s || e < l) return -inf;
if (l <= s && e <= r) return treemax[node];
int m = s + e >> 1;
int t1 = querymax(node * 2, s, m, l, r);
int t2 = querymax(node * 2 + 1, m + 1, e, l, r);
return max(t1, t2);
}
//HLD - function
void dfs(int v = 1) {
chk[v] = 1;
for (auto i: inp[v]) {
if (chk[i]) continue;
chk[i] = 1;
g[v].push_back(i);
dfs(i);
}
}
void dfs1(int v = 1) {
sz[v] = 1;
for (auto &i: g[v]) {
dep[i] = dep[v] + 1;
par[i] = v;
dfs1(i);
sz[v] += sz[i];
if (sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
}
}
void dfs2(int v = 1) {
in[v] = ++pv;
for (auto i: g[v]) {
top[i] = i == g[v][0] ? top[v] : i;
dfs2(i);
}
}
void update(int a, int b, int op, int k) {
while (top[a] != top[b]) {
if (dep[top[a]] < dep[top[b]]) swap(a, b);
int st = top[a];
if (op == 1) updatemin(1, 1, n, in[st], in[a], k);
else updatemax(1, 1, n, in[st], in[a], k);
a = par[st];
}
if (dep[a] > dep[b]) swap(a, b);
if (op == 1) updatemin(1, 1, n, in[a] + 1, in[b], k);
else updatemax(1, 1, n, in[a] + 1, in[b], k);
}
vector<int> bench[70707];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 2; i <= n; i++) {
int s, e;
cin >> s >> e;
inp[s].push_back(e);
inp[e].push_back(s);
}
dfs();
dfs1();
dfs2();
cin >> q;
for (int i = 1; i < (1 << 18); i++) {
tmpmin[i] = inf;
tmpmax[i] = -inf;
treemin[i] = inf;
treemax[i] = -inf;
}
vector<int> zz;
for (int i = 0; i < q; i++) {
char op;
int a, b, c;
cin >> op >> a >> b >> c;
if (op == 'm') update(a, b, 2, c);
else update(a, b, 1, c);
zz.push_back(c);
}
sort(zz.begin(), zz.end());
zz.resize(unique(zz.begin(), zz.end()) - zz.begin());
memset(mx, -1, sizeof(mx));
memset(mn, -1, sizeof(mn));
for (int i = 2; i <= n; i++) {
int mini = querymax(1, 1, n, in[i], in[i]);
int maxi = querymin(1, 1, n, in[i], in[i]);
if (mini != inf) {
mn[i] = lower_bound(zz.begin(), zz.end(), mini) - zz.begin();
bench[mn[i]].push_back(i);
}
if (maxi != -inf) {
mx[i] = lower_bound(zz.begin(), zz.end(), maxi) - zz.begin();
bench[mx[i]].push_back(i);
}
}
set<pair<int, int>> s;
for (int i = 0; i < zz.size(); ++i) {
cnt[i] = bench[i].size();
s.insert({bench[i].size(), i});
}
for (auto &i: ans) i = inf;
while (!s.empty()) {
int id = s.begin()->second;
s.erase(s.begin());
chk[id] = 1;
int v = 0;
for (auto node: bench[id])
if (ans[node] == inf) {
v = node;
break;
}
if (mn[v] != -1 && !chk[mn[v]]) {
s.erase({cnt[mn[v]], mn[v]});
cnt[mn[v]]--;
s.insert({cnt[mn[v]], mn[v]});
}
if (mx[v] != -1 && !chk[mx[v]]) {
s.erase({cnt[mx[v]], mx[v]});
cnt[mx[v]]--;
s.insert({cnt[mx[v]], mx[v]});
}
ans[v] = zz[id];
}
for (int i = 2; i <= n; ++i) {
cout << i << ' ' << par[i] << ' ';
if (ans[i] != inf)
cout << ans[i];
else {
if (mn[i] != -1) {
cout << zz[mn[i]];
} else {
cout << 0;
}
}
cout << '\n';
}
}
Compilation message
minmaxtree.cpp: In function 'void updatemin(int, int, int, int, int, int)':
minmaxtree.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int m = s + e >> 1;
| ~~^~~
minmaxtree.cpp: In function 'void updatemax(int, int, int, int, int, int)':
minmaxtree.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int m = s + e >> 1;
| ~~^~~
minmaxtree.cpp: In function 'int querymin(int, int, int, int, int)':
minmaxtree.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int m = s + e >> 1;
| ~~^~~
minmaxtree.cpp: In function 'int querymax(int, int, int, int, int)':
minmaxtree.cpp:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
99 | int m = s + e >> 1;
| ~~^~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int i = 0; i < zz.size(); ++i) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
28616 KB |
Output is correct |
| 2 |
Correct |
177 ms |
24264 KB |
Output is correct |
| 3 |
Correct |
164 ms |
26776 KB |
Output is correct |
| 4 |
Correct |
149 ms |
29996 KB |
Output is correct |
| 5 |
Correct |
162 ms |
25980 KB |
Output is correct |
| 6 |
Correct |
173 ms |
25752 KB |
Output is correct |
| 7 |
Correct |
139 ms |
25032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
20808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
