#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
// ---------- Graph / HLD ----------
struct Edge {
int to, id;
};
int n;
vector<vector<Edge>> g;
vector<int> parent_, depth_, heavy, sz, head, pos;
vector<int> invPos; // pos -> node
vector<int> edgeIdAtPos; // pos -> original edge id (for edge mapped to child node)
int curPos;
int dfs_sz(int v, int p) {
parent_[v] = p;
sz[v] = 1;
heavy[v] = -1;
int best = 0;
for (auto& e : g[v]) {
if (e.to == p) continue;
depth_[e.to] = depth_[v] + 1;
int s = dfs_sz(e.to, v);
if (s > best) {
best = s;
heavy[v] = e.to;
}
sz[v] += s;
}
return sz[v];
}
void dfs_hld(int v, int h, int pedge_id = -1) {
head[v] = h;
pos[v] = ++curPos;
invPos[pos[v]] = v;
if (pedge_id != -1) edgeIdAtPos[pos[v]] = pedge_id; // map edge (v-parent[v]) to pos[v]
if (heavy[v] != -1) {
int hid = -1;
for (auto& e : g[v])
if (e.to == heavy[v]) {
hid = e.id;
break;
}
dfs_hld(heavy[v], h, hid);
}
for (auto& e : g[v]) {
if (e.to == parent_[v] || e.to == heavy[v]) continue;
dfs_hld(e.to, e.to, e.id);
}
}
// ---------- Segment tree supporting range chmax ----------
struct SegChMax {
int n;
vector<int> st, lazy;
SegChMax(int _n = 0) { init(_n); }
void init(int _n) {
n = 1;
while (n < _n)
n <<= 1;
st.assign(2 * n, -INF);
lazy.assign(2 * n, -INF);
}
void apply(int v, int x) {
st[v] = max(st[v], x);
lazy[v] = max(lazy[v], x);
}
void push(int v) {
if (lazy[v] != -INF) {
apply(v << 1, lazy[v]);
apply(v << 1 | 1, lazy[v]);
lazy[v] = -INF;
}
}
void update(int v, int l, int r, int ql, int qr, int x) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
apply(v, x);
return;
}
push(v);
int m = (l + r) >> 1;
update(v << 1, l, m, ql, qr, x);
update(v << 1 | 1, m + 1, r, ql, qr, x);
// st[v] aggregation value unused
}
void update_range(int l, int r, int x) {
if (l > r) return;
update(1, 1, n, l, r, x);
}
int query_point(int v, int l, int r, int p) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (p <= m)
return query_point(v << 1, l, m, p);
else
return query_point(v << 1 | 1, m + 1, r, p);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
// ---------- Segment tree supporting range chmin ----------
struct SegChMin {
int n;
vector<int> st, lazy;
SegChMin(int _n = 0) { init(_n); }
void init(int _n) {
n = 1;
while (n < _n)
n <<= 1;
st.assign(2 * n, INF);
lazy.assign(2 * n, INF);
}
void apply(int v, int x) {
st[v] = min(st[v], x);
lazy[v] = min(lazy[v], x);
}
void push(int v) {
if (lazy[v] != INF) {
apply(v << 1, lazy[v]);
apply(v << 1 | 1, lazy[v]);
lazy[v] = INF;
}
}
void update(int v, int l, int r, int ql, int qr, int x) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
apply(v, x);
return;
}
push(v);
int m = (l + r) >> 1;
update(v << 1, l, m, ql, qr, x);
update(v << 1 | 1, m + 1, r, ql, qr, x);
// st[v] aggregation value unused
}
void update_range(int l, int r, int x) {
if (l > r) return;
update(1, 1, n, l, r, x);
}
int query_point(int v, int l, int r, int p) {
if (l == r) return st[v];
push(v);
int m = (l + r) >> 1;
if (p <= m)
return query_point(v << 1, l, m, p);
else
return query_point(v << 1 | 1, m + 1, r, p);
}
int query_point(int p) { return query_point(1, 1, n, p); }
};
// Update all edges on path u-v with either chmax (lower) or chmin (upper)
inline void update_path_edges(int u, int v, int x, bool isLower, SegChMax& segL, SegChMin& segU) {
while (head[u] != head[v]) {
if (depth_[head[u]] < depth_[head[v]]) swap(u, v);
int h = head[u];
if (isLower)
segL.update_range(pos[h], pos[u], x);
else
segU.update_range(pos[h], pos[u], x);
u = parent_[h];
}
if (depth_[u] < depth_[v]) swap(u, v);
if (pos[v] + 1 <= pos[u]) {
if (isLower)
segL.update_range(pos[v] + 1, pos[u], x);
else
segU.update_range(pos[v] + 1, pos[u], x);
}
}
// Visit path segments (in position space), calling op(l, r, chainHeadNode)
template<class F>
inline void for_each_path_segment(int u, int v, const F& op) {
while (head[u] != head[v]) {
if (depth_[head[u]] < depth_[head[v]]) swap(u, v);
int h = head[u];
op(pos[h], pos[u], h);
u = parent_[h];
}
if (depth_[u] < depth_[v]) swap(u, v);
if (pos[v] + 1 <= pos[u]) {
int h = head[u];
op(pos[v] + 1, pos[u], h);
}
}
// ---------- Hopcroft-Karp ----------
struct HopcroftKarp {
int nL, nR;
vector<vector<int>> adj;
vector<int> dist, pairU, pairV, it;
HopcroftKarp(int _nL = 0, int _nR = 0) { init(_nL, _nR); }
void init(int _nL, int _nR) {
nL = _nL;
nR = _nR;
adj.assign(nL, {});
pairU.assign(nL, -1);
pairV.assign(nR, -1);
dist.resize(nL);
it.resize(nL);
}
inline void addEdge(int u, int v) { adj[u].push_back(v); }
bool bfs() {
queue<int> q;
bool reachable = false;
for (int u = 0; u < nL; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
q.push(u);
} else
dist[u] = -1;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
int pu = pairV[v];
if (pu != -1 && dist[pu] == -1) {
dist[pu] = dist[u] + 1;
q.push(pu);
}
if (pu == -1) reachable = true;
}
}
return reachable;
}
bool dfs(int u) {
for (int& k = it[u]; k < (int)adj[u].size(); ++k) {
int v = adj[u][k];
int pu = pairV[v];
if (pu == -1 || (dist[pu] == dist[u] + 1 && dfs(pu))) {
pairU[u] = v;
pairV[v] = u;
return true;
}
}
dist[u] = -1;
return false;
}
int maxMatching() {
int matching = 0;
while (bfs()) {
fill(it.begin(), it.end(), 0);
for (int u = 0; u < nL; u++)
if (pairU[u] == -1)
if (dfs(u)) matching++;
}
return matching;
}
};
// ---------- main ----------
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
g.assign(n + 1, {});
vector<pair<int, int>> edges(n); // edges[1..n-1]
for (int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
edges[i] = {a, b};
g[a].push_back({b, i});
g[b].push_back({a, i});
}
parent_.assign(n + 1, 0);
depth_.assign(n + 1, 0);
heavy.assign(n + 1, -1);
sz.assign(n + 1, 0);
head.assign(n + 1, 0);
pos.assign(n + 1, 0);
invPos.assign(n + 2, 0);
edgeIdAtPos.assign(n + 2, -1);
curPos = 0;
depth_[1] = 0;
dfs_sz(1, 0);
dfs_hld(1, 1, -1);
int q;
cin >> q;
struct Q {
char type;
int u, v, x, id;
};
vector<Q> queries;
queries.reserve(q);
for (int i = 0; i < q; i++) {
char t;
int u, v, x;
cin >> t >> u >> v >> x;
queries.push_back({t, u, v, x, i});
}
// Segment trees for bounds
SegChMax segL(n + 5);
SegChMin segU(n + 5);
// Apply constraints
for (auto& qu : queries) {
if (qu.type == 'm') { // path min == x -> all edges >= x
update_path_edges(qu.u, qu.v, qu.x, true, segL, segU);
} else { // path max == x -> all edges <= x
update_path_edges(qu.u, qu.v, qu.x, false, segL, segU);
}
}
// Collect bounds per position
vector<int> Lpos(n + 2), Upos(n + 2);
for (int p = 1; p <= n; p++) {
Lpos[p] = segL.query_point(p);
Upos[p] = segU.query_point(p);
}
// Feasibility
for (int p = 2; p <= n; p++) { // only edges (pos>=2) matter
if (Lpos[p] > Upos[p]) {
cout << -1 << "\n";
return 0;
}
}
// Prepare chain indexing for fast per-chain sets
vector<int> chainIndex(n + 1, -1);
int chains = 0;
for (int v = 1; v <= n; v++) {
if (head[v] == v) chainIndex[v] = chains++;
}
// Active positions per chain for current x
vector<set<int>> active(chains);
// Positions (edges only) with their [L,U] and chain id
struct PInfo {
int p, L, U, cidx;
};
vector<PInfo> pinfos;
pinfos.reserve(n - 1);
for (int p = 2; p <= n; p++) {
int node = invPos[p];
int h = head[node];
int cidx = chainIndex[h];
// Only real edges (edgeIdAtPos[p]!=-1)
if (edgeIdAtPos[p] != -1) {
pinfos.push_back({p, Lpos[p], Upos[p], cidx});
}
}
// Sort positions by L ascending for activation, and by U ascending for deactivation
vector<int> orderByL(pinfos.size()), orderByU(pinfos.size());
iota(orderByL.begin(), orderByL.end(), 0);
iota(orderByU.begin(), orderByU.end(), 0);
sort(orderByL.begin(), orderByL.end(), [&](int a, int b) { return pinfos[a].L < pinfos[b].L; });
sort(orderByU.begin(), orderByU.end(), [&](int a, int b) { return pinfos[a].U < pinfos[b].U; });
// Sort queries by x (remember original ids)
vector<int> qord(q);
iota(qord.begin(), qord.end(), 0);
sort(qord.begin(), qord.end(), [&](int a, int b) { return queries[a].x < queries[b].x; });
// Build HK graph while sweeping x
int mEdges = n - 1;
HopcroftKarp hk(q, mEdges);
int aptr = 0, rptr = 0; // activation & removal pointers
for (int idx : qord) {
int x = queries[idx].x;
// Activate positions with L <= x
while (aptr < (int)orderByL.size() && pinfos[orderByL[aptr]].L <= x) {
const auto& pf = pinfos[orderByL[aptr]];
if (pf.L <= pf.U) active[pf.cidx].insert(pf.p);
++aptr;
}
// Deactivate positions with U < x
while (rptr < (int)orderByU.size() && pinfos[orderByU[rptr]].U < x) {
const auto& pf = pinfos[orderByU[rptr]];
auto it = active[pf.cidx].find(pf.p);
if (it != active[pf.cidx].end()) active[pf.cidx].erase(it);
++rptr;
}
// For this query, walk its path in O(log^2 n) segments,
// and in each segment iterate ONLY active positions
auto add_in_segment = [&](int l, int r, int chainHead) {
int cidx = chainIndex[chainHead];
auto& S = active[cidx];
auto it = S.lower_bound(l);
while (it != S.end() && *it <= r) {
int p = *it;
int eId = edgeIdAtPos[p]; // 1..mEdges
if (eId != -1) {
hk.addEdge(queries[idx].id, eId - 1); // left: original query id; right: 0-based edge id
}
++it;
}
};
for_each_path_segment(queries[idx].u, queries[idx].v, add_in_segment);
}
// Run matching
int matching = hk.maxMatching();
if (matching < q) {
cout << -1 << "\n";
return 0;
}
// Build reverse map edgeId -> pos
vector<int> edgePos(mEdges + 1, -1);
for (int p = 1; p <= n; p++) {
int eid = edgeIdAtPos[p];
if (eid != -1) edgePos[eid] = p;
}
// Construct weights for edges
vector<int> weight(n, 1000000000);
for (int e = 1; e <= mEdges; e++) {
int matchedQuery = hk.pairV[e - 1]; // query id
int p = edgePos[e];
if (matchedQuery != -1) {
weight[e] = queries[matchedQuery].x;
} else {
int chosen;
if (Lpos[p] != -INF)
chosen = Lpos[p];
else if (Upos[p] != INF)
chosen = Upos[p];
else
chosen = 1000000000;
if (chosen < Lpos[p]) chosen = Lpos[p];
if (chosen > Upos[p]) chosen = Upos[p];
weight[e] = chosen;
}
}
// Output in input edge order
for (int i = 1; i <= mEdges; i++) {
cout << edges[i].first << ' ' << edges[i].second << ' ' << weight[i] << '\n';
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
