#include<bits/stdc++.h>
using namespace std;
const int MN = 200010;
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4 * MN, 2e9);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = min(tree[2*n], tree[2*n + 1]);
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 2e9;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return min(L, R);
}
} bit;
int N, M;
vector<int> adj[MN];
int lo[MN], hi[MN];
int par[20][MN], dep[MN], tin[MN], tout[MN], invt[MN], timer;
void dfs0(int u, int p) {
tin[u] = timer++;
par[0][u] = p;
for(int i = 1; i < 20; i++) {
int t = par[i - 1][u];
if(t == -1) break;
par[i][u] = par[i - 1][t];
}
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(v == p) continue;
dep[v] = dep[u] + 1;
dfs0(v, u);
}
tout[u] = timer;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int diff = dep[a] - dep[b];
for(int i = 0; i < 20; i++) if(diff & (1 << i)) a = par[i][a];
if(a == b) return a;
for(int i = 20; i--;) {
if(par[i][a] != par[i][b]) {
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
struct Query {
char t;
int x, w, z;
bool operator <(const Query &i) const {
if(tin[x] != tin[i.x]) return tin[x] < tin[i.x];
if(w != i.w) return w < i.w;
if(z != i.z) return z < i.z;
return false;
}
};
vector<Query> query;
unordered_map<int, int> H;
int Z[MN];
vector<int> rem[MN];
void dfs1(int u, int p) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(v == p) continue;
dfs1(v, u);
}
for(int i = 0; i < rem[u].size(); i++) {
bit.upd(rem[u][i], 2e9, 0, MN - 1, 1);
}
if(p != -1) {
int a = lower_bound(query.begin(), query.end(), (Query){ 'M', u, -1, -1 }) - query.begin();
int b = lower_bound(query.begin(), query.end(), (Query){ 'M', invt[ tout[u] - 1 ], (int)1e9, (int)1e9 }) - query.begin() - 1;
hi[u] = bit.quer(a, b, 0, MN - 1, 1);
}
}
void dfs2(int u, int p) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(v == p) continue;
dfs2(v, u);
}
for(int i = 0; i < rem[u].size(); i++) {
bit.upd(rem[u][i], 2e9, 0, MN - 1, 1);
}
if(p != -1) {
int a = lower_bound(query.begin(), query.end(), (Query){ 'm', u, -1, -1 }) - query.begin();
int b = lower_bound(query.begin(), query.end(), (Query){ 'm', invt[ tout[u] - 1 ], (int)1e9, (int)1e9 }) - query.begin() - 1;
lo[u] = -bit.quer(a, b, 0, MN - 1, 1);
}
}
vector<int> bip[MN << 1];
queue<int> q;
int vis[MN << 1], deg[MN << 1], ans[MN];
void dfs3(int u) {
vis[u] = 1;
for(int i = 0; i < bip[u].size(); i++) {
int v = bip[u][i];
if(vis[v]) continue;
if(v < N) {
ans[v] = u - N;
}
dfs3(v);
return;
}
}
void max_matching() {
for(int i = 0; i < M; i++) deg[N + i] = bip[N + i].size();
for(int i = 0; i < M; i++) if(deg[N + i] == 1) {
q.push(N + i);
vis[N + i] = 1;
}
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < bip[u].size(); i++) {
int v = bip[u][i];
if(vis[v]) continue;
vis[v] = 1;
ans[v] = u - N;
for(int j = 0; j < bip[v].size(); j++) {
int w = bip[v][j];
if(w == u) continue;
deg[w]--;
if(deg[w] == 1) {
q.push(w);
vis[w] = 1;
}
}
}
}
for(int i = 0; i < M; i++) if(!vis[N + i]) {
dfs3(N + i);
}
}
int main() {
scanf("%d", &N);
for(int i = 0; i < N - 1; i++) {
int u, v; scanf("%d %d", &u, &v);
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(par, -1, sizeof(par));
dfs0(0, -1);
for(int i = 0; i < N; i++) invt[tin[i]] = i;
scanf("%d", &M);
for(int i = 0; i < M; i++) {
char t; int x, y, z; scanf("\n%c %d %d %d", &t, &x, &y, &z);
x--; y--;
int w = lca(x, y);
query.push_back({ t, x, w, z });
query.push_back({ t, y, w, z });
H[z] = i;
Z[i] = z;
}
sort(query.begin(), query.end());
bit.init();
for(int i = 0; i < query.size(); i++) {
if(query[i].t == 'M') {
bit.upd(i, query[i].z, 0, MN - 1, 1);
rem[ query[i].w ].push_back(i);
}
}
dfs1(0, -1);
for(int i = 0; i < N; i++) rem[i].clear();
bit.init();
for(int i = 0; i < query.size(); i++) {
if(query[i].t == 'm') {
bit.upd(i, -query[i].z, 0, MN - 1, 1);
rem[ query[i].w ].push_back(i);
}
}
dfs2(0, -1);
/*
for(int i = 1; i < N; i++) {
cout << lo[i] << ' ' << hi[i] << endl;
}
//*/
for(int i = 1; i < N; i++) {
if(lo[i] != -2e9) {
bip[i].push_back(N + H[ lo[i] ]);
bip[ N + H[ lo[i] ] ].push_back(i);
}
if(hi[i] != 2e9) {
bip[i].push_back(N + H[ hi[i] ]);
bip[ N + H[ hi[i] ] ].push_back(i);
}
}
memset(ans, -1, sizeof(ans));
max_matching();
for(int i = 1; i < N; i++) {
if(ans[i] == -1) printf("%d %d %d\n", i + 1, par[0][i] + 1, hi[i]);
else printf("%d %d %d\n", i + 1, par[0][i] + 1, Z[ ans[i] ]);
}
}
Compilation message
minmaxtree.cpp: In function 'void dfs0(int, int)':
minmaxtree.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs1(int, int)':
minmaxtree.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rem[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs2(int, int)':
minmaxtree.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < rem[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs3(int)':
minmaxtree.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < bip[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void max_matching()':
minmaxtree.cpp:145:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < bip[u].size(); i++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp:151:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < bip[v].size(); j++) {
~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:199:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < query.size(); i++) {
~~^~~~~~~~~~~~~~
minmaxtree.cpp:210:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < query.size(); i++) {
~~^~~~~~~~~~~~~~
minmaxtree.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
minmaxtree.cpp:172:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
minmaxtree.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
~~~~~^~~~~~~~~~
minmaxtree.cpp:186:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char t; int x, y, z; scanf("\n%c %d %d %d", &t, &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
41080 KB |
Output is correct |
| 2 |
Correct |
37 ms |
41080 KB |
Output is correct |
| 3 |
Correct |
38 ms |
41196 KB |
Output is correct |
| 4 |
Correct |
37 ms |
41228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
499 ms |
60932 KB |
Output is correct |
| 2 |
Correct |
396 ms |
60932 KB |
Output is correct |
| 3 |
Correct |
401 ms |
62068 KB |
Output is correct |
| 4 |
Correct |
365 ms |
69240 KB |
Output is correct |
| 5 |
Correct |
341 ms |
69240 KB |
Output is correct |
| 6 |
Correct |
351 ms |
69240 KB |
Output is correct |
| 7 |
Correct |
354 ms |
70264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
70264 KB |
Output is correct |
| 2 |
Correct |
203 ms |
70264 KB |
Output is correct |
| 3 |
Correct |
288 ms |
70264 KB |
Output is correct |
| 4 |
Correct |
227 ms |
70264 KB |
Output is correct |
| 5 |
Correct |
248 ms |
70264 KB |
Output is correct |
| 6 |
Correct |
306 ms |
70264 KB |
Output is correct |
| 7 |
Correct |
309 ms |
70264 KB |
Output is correct |
| 8 |
Correct |
306 ms |
70264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
41080 KB |
Output is correct |
| 2 |
Correct |
37 ms |
41080 KB |
Output is correct |
| 3 |
Correct |
38 ms |
41196 KB |
Output is correct |
| 4 |
Correct |
37 ms |
41228 KB |
Output is correct |
| 5 |
Correct |
499 ms |
60932 KB |
Output is correct |
| 6 |
Correct |
396 ms |
60932 KB |
Output is correct |
| 7 |
Correct |
401 ms |
62068 KB |
Output is correct |
| 8 |
Correct |
365 ms |
69240 KB |
Output is correct |
| 9 |
Correct |
341 ms |
69240 KB |
Output is correct |
| 10 |
Correct |
351 ms |
69240 KB |
Output is correct |
| 11 |
Correct |
354 ms |
70264 KB |
Output is correct |
| 12 |
Correct |
206 ms |
70264 KB |
Output is correct |
| 13 |
Correct |
203 ms |
70264 KB |
Output is correct |
| 14 |
Correct |
288 ms |
70264 KB |
Output is correct |
| 15 |
Correct |
227 ms |
70264 KB |
Output is correct |
| 16 |
Correct |
248 ms |
70264 KB |
Output is correct |
| 17 |
Correct |
306 ms |
70264 KB |
Output is correct |
| 18 |
Correct |
309 ms |
70264 KB |
Output is correct |
| 19 |
Correct |
306 ms |
70264 KB |
Output is correct |
| 20 |
Correct |
405 ms |
71996 KB |
Output is correct |
| 21 |
Correct |
299 ms |
72308 KB |
Output is correct |
| 22 |
Correct |
380 ms |
74364 KB |
Output is correct |
| 23 |
Correct |
390 ms |
76348 KB |
Output is correct |
| 24 |
Correct |
511 ms |
86404 KB |
Output is correct |
| 25 |
Correct |
423 ms |
90920 KB |
Output is correct |
| 26 |
Correct |
349 ms |
92020 KB |
Output is correct |
| 27 |
Correct |
375 ms |
92304 KB |
Output is correct |
| 28 |
Correct |
532 ms |
92304 KB |
Output is correct |
| 29 |
Correct |
457 ms |
93860 KB |
Output is correct |
| 30 |
Correct |
307 ms |
93960 KB |
Output is correct |
| 31 |
Correct |
428 ms |
96176 KB |
Output is correct |
| 32 |
Correct |
435 ms |
99572 KB |
Output is correct |
| 33 |
Correct |
318 ms |
100556 KB |
Output is correct |
| 34 |
Correct |
432 ms |
102852 KB |
Output is correct |
| 35 |
Correct |
405 ms |
104384 KB |
Output is correct |
