#include<bits/stdc++.h>
using namespace std;
const int MN = 70010;
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();
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();
lo[u] = -bit.quer(a, b, 0, MN - 1, 1);
}
}
vector<int> bip[MN << 1];
queue<int> q;
int vis[MN << 1], deg[MN], 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[i] = bip[N + i].size();
for(int i = 0; i < M; i++) if(deg[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(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);
}
}
max_matching();
for(int i = 1; i < N; i++) {
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:198:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < query.size(); i++) {
~~^~~~~~~~~~~~~~
minmaxtree.cpp:209:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < query.size(); i++) {
~~^~~~~~~~~~~~~~
minmaxtree.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
minmaxtree.cpp:171: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:182:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
~~~~~^~~~~~~~~~
minmaxtree.cpp:185: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 |
Incorrect |
14 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
35700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
35700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
