#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 200000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;
int n, m, mn[N], mx[N], par[N][LOG], sz[N], h[N], ans[N], mark[N], W[N], M[N], H[N], PAR[N], PARE[N], M2[N];
vector<pii> G[N], g[N];
vector<int> Tah[2][N], Sar[2][N];
multiset<int> st[2][N];
vector<pii> EE;
map<int, int> mp;
vector<pii> yal;
bool ff = 0;
void DFS(int v = 1, int p = 0){
par[v][0] = p;
for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
for (auto u:G[v]){
if (u.F == p) continue;
h[u.F] = h[v] + 1;
DFS(u.F,v);
}
}
void dfssz(int v = 1, int p = 0){
for (auto u:G[v]){
if(u.F == p) continue;
dfssz(u.F, v);
sz[v] += sz[u.F];
}
}
int LCA(int v, int u){
if (h[v] < h[u]) swap(v, u);
int res = h[v] - h[u];
for (int i = 0; i < LOG; i++) if (res & (1 << i)) v = par[v][i];
if (v == u) return v;
for (int i = LOG - 1; i >= 0; i--){
if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
}
return par[v][0];
}
void dfs(int v = 1, int p = 0, int w = 0){
if (G[v].size() == 1 && v != 1){
for (int j = 0; j < 2; j++){
for (auto u:Tah[j][v]) st[j][v].insert(u);
for (auto u:Sar[j][v]) st[j][v].erase(st[j][v].find(u));
}
if (st[0][v].size()){
mx[w] = *st[0][v].begin();
}
if (st[1][v].size()){
mn[w] = *st[1][v].rbegin();
}
return;
}
int MX = 0;
for (auto u:G[v]){
if(u.F == p) continue;
dfs(u.F, v, u.S);
if (sz[MX] < sz[u.F]) MX = u.F;
}
for (int j = 0; j < 2; j++){
st[j][v].swap(st[j][MX]);
for (auto u:Tah[j][v]) st[j][v].insert(u);
}
for (auto u:G[v]){
if(u.F == p || u.F == MX) continue;
for (int j = 0; j < 2; j++){
for (auto x:st[j][u.F]){
st[j][v].insert(x);
}
st[j][u.F].clear();
}
}
for (auto u:Sar[0][v]){
st[0][v].erase(st[0][v].find(u));
}
for (auto u:Sar[1][v]){
st[1][v].erase(st[1][v].find(u));
}
if (st[0][v].size()){
mx[w] = *st[0][v].begin();
if (v == 1) assert(0);
}
if(st[1][v].size()){
mn[w] = *st[1][v].rbegin();
if (v == 1) assert(0);
}
}
inline int Query(int w){
return mp[w];
}
void DFS2(int v){
M[v] = 1;
mark[v] = 1;
for (auto u:g[v]){
if (!M[u.F] && !mark[u.F]){
DFS2(u.F);
//cout << "YES " << u.F << ' ' << u.S << ' ' << W[u.F] << '\n';
ans[u.S] = W[u.F];
}
}
}
void DFS3(int v){
M2[v] = 1;
//cout << v << ' ' << PARE[v] << '\n';
for(auto u:g[v]){
if (!M2[u.F]){
H[u.F] = H[v] + 1;
PAR[u.F] = v, PARE[u.F] = u.S;
DFS3(u.F);
}else if((H[u.F] < H[v]) && ff == 0 && (u.S != PARE[v])){
//cout << "YES" << endl;
ff = 1;
//cout << u.S << '\n';
ans[u.S] = W[v];
while (v != u.F){
mark[v] = 1;
// cout << "YES\n";
ans[PARE[v]] = W[PAR[v]];
v = PAR[v];
}
mark[u.F] = 1;
}
}
}
void DFS4(int v){
M[v] = 1;
for (auto u:g[v]){
if (!M[u.F] && !mark[u.F]){
ans[u.S] = W[u.F];
DFS4(u.F);
}
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
sz[0] = -INF;
fill(mn, mn + N, -INF), fill(mx, mx + N, -INF);
for (int i = 1; i <= n - 1; i++){
int v, u;
cin >> v >> u;
yal.pb({v, u});
G[v].pb({u, i}), G[u].pb({v, i});
}
cin >> m;
DFS();
for (int i = 1; i <= m; i++){
char c;
int v, u, w;
cin >> c >> v >> u >> w;
int lca = LCA(v, u);
int C = (c == 'm');
Tah[C][v].pb(w), Tah[C][u].pb(w), Sar[C][lca].pb(w), Sar[C][lca].pb(w);
sz[v]++, sz[u]++, sz[lca]-=2;
EE.pb({w, i});
W[i] = w;
mp[w] = i;
}
dfssz();
dfs();
// for (int i = 0; i < n - 1; i++) cout << mn[i] << ' ' << mx[i] << '\n';
for (int i = 1; i <= n - 1; i++){
if (mx[i] == -INF || mn[i] == -INF){
//cout << "YES" << ' ' << mx[i] << ' ' << mn[i] << endl;
if (mx[i] == -INF && mn[i] != -INF){
mark[Query(mn[i])] = 1, ans[i] = mn[i];
// cout << "YES\n" << Query(mn[i]) << endl;
}
if (mx[i] != -INF && mn[i] == -INF) mark[Query(mx[i])] = 1, ans[i] = mx[i];
}else{
g[Query(mx[i])].pb({Query(mn[i]), i});
g[Query(mn[i])].pb({Query(mx[i]), i});
//cout << Query(mn[i]) << ' ' << Query(mx[i]) << '\n';
}
}
for (int i = 1; i <= m; i++){
if (mark[i] == 1 && M[i] == 0){
DFS2(i);
// cout << "YES " << i << endl;
}
}
//cout << "YES" << endl;
for (int i = 1; i <= m; i++){
if (!M[i] && !M2[i]){
ff = 0;
// cout << "YES2" << endl;
DFS3(i);
}
}
//cout << "YES" << endl;
for (int i = 1; i <= m; i++){
if (mark[i] && !M[i]) DFS4(i);
}
for (int i = 0; i < n - 1; i++){
cout << yal[i].F << ' ' << yal[i].S << ' ' << ans[i + 1] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
31 ms |
48888 KB |
Output is correct |
| 3 |
Correct |
31 ms |
48896 KB |
Output is correct |
| 4 |
Correct |
29 ms |
48896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
366 ms |
74700 KB |
Output is correct |
| 2 |
Correct |
344 ms |
68460 KB |
Output is correct |
| 3 |
Correct |
359 ms |
74964 KB |
Output is correct |
| 4 |
Correct |
381 ms |
76908 KB |
Output is correct |
| 5 |
Correct |
353 ms |
72044 KB |
Output is correct |
| 6 |
Correct |
346 ms |
69140 KB |
Output is correct |
| 7 |
Correct |
322 ms |
68200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
63724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
48896 KB |
Output is correct |
| 2 |
Correct |
31 ms |
48888 KB |
Output is correct |
| 3 |
Correct |
31 ms |
48896 KB |
Output is correct |
| 4 |
Correct |
29 ms |
48896 KB |
Output is correct |
| 5 |
Correct |
366 ms |
74700 KB |
Output is correct |
| 6 |
Correct |
344 ms |
68460 KB |
Output is correct |
| 7 |
Correct |
359 ms |
74964 KB |
Output is correct |
| 8 |
Correct |
381 ms |
76908 KB |
Output is correct |
| 9 |
Correct |
353 ms |
72044 KB |
Output is correct |
| 10 |
Correct |
346 ms |
69140 KB |
Output is correct |
| 11 |
Correct |
322 ms |
68200 KB |
Output is correct |
| 12 |
Incorrect |
191 ms |
63724 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
