#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define int long long int
using namespace std;
const int64_t INF = 1e17;
const int mod = 1e9+7;
vector<int> tree[100001];
struct LCA {
vector<int> height, euler, first, segtree;
vector<bool> visited;
int n;
LCA(int n) : n(n) {
height.resize(n + 1);
first.resize(n + 1, -1);
euler.reserve(n * 2);
visited.assign(n + 1, false);
}
void dfs(int node, int h = 0) {
visited[node] = true;
height[node] = h;
first[node] = euler.size();
euler.push_back(node);
for (auto to : tree[node]) {
if (!visited[to]) {
dfs(to, h + 1);
euler.push_back(node);
}
}
}
int build(int node, int b, int e) {
if (b == e) {
return segtree[node] = euler[b];
} else {
int mid = (b + e) / 2;
int left = build(node * 2, b, mid);
int right = build(node * 2 + 1, mid + 1, e);
return segtree[node] = (height[left] < height[right] ? left : right);
}
}
void init() {
dfs(1);
int m = euler.size();
segtree.assign(m * 4, -1);
build(1, 0, m - 1);
}
int query(int node, int b, int e, int L, int R) {
if (b > R || e < L)
return -1;
if (b >= L && e <= R)
return segtree[node];
int mid = (b + e) / 2;
int left = query(node * 2, b, mid, L, R);
int right = query(node * 2 + 1, mid + 1, e, L, R);
if (left == -1) return right;
if (right == -1) return left;
return height[left] < height[right] ? left : right;
}
int lca(int u, int v) {
int left = first[u], right = first[v];
if (left > right)
swap(left, right);
return query(1, 0, euler.size() - 1, left, right);
}
};
struct Dinic {
struct Edge {
int to, cap, rev;
};
vector<vector<Edge>> G;
vector<int> level, iter;
Dinic(int n) : G(n), level(n), iter(n) {}
void add_edge(int from, int to, int cap) {
G[from].push_back({to, cap, (int)G[to].size()});
G[to].push_back({from, 0, (int)G[from].size() - 1});
}
void bfs(int s) {
fill(level.begin(), level.end(), -1);
queue<int> que;
level[s] = 0;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto &e : G[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int &i = iter[v]; i < (int)G[v].size(); i++) {
Edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
fill(iter.begin(), iter.end(), 0);
int f;
while ((f = dfs(s, t, INT_MAX)) > 0) {
flow += f;
}
}
}
set<pair<int, int>> get_full_edges() {
set<pair<int, int>> full_edges;
for (int i = 0; i < G.size(); i++) {
for (auto &e : G[i]) {
if (e.cap == 0) {
full_edges.insert({i, e.to});
}
}
}
return full_edges;
}
};
const int MAXN = 1e5 + 5;
vector<pair<int, int>> edges;
map<int, int> enumerate_assignments;
map<pair<int, int>, int> enumerate_edges;
map<pair<int, int>, int> max_assignments;
map<pair<int, int>, int> min_assignments;
vector<int> max_lcas[MAXN];
vector<int> min_lcas[MAXN];
vector<int> max_removals[MAXN];
vector<int> min_removals[MAXN];
struct Query {
char type;
int u, v, z;
};
vector<Query> queries;
void assign_max(int u, int p, multiset<int>& assignments) {
for (auto v : max_lcas[u]) {
assignments.insert(v);
}
for (auto v : max_removals[u]) {
assignments.erase(assignments.find(v));
}
for (int v : tree[u]) {
if (v == p) continue;
if (!assignments.empty())
max_assignments[{min(u, v), max(u, v)}] = *assignments.begin();
assign_max(v, u, assignments);
}
}
void assign_min(int u, int p, multiset<int>& assignments) {
for (auto v : min_lcas[u]) {
assignments.insert(v);
}
for (auto v : min_removals[u]) {
assignments.erase(assignments.find(v));
}
for (int v : tree[u]) {
if (v == p) continue;
if (!assignments.empty())
min_assignments[{min(u, v), max(u, v)}] = *assignments.rbegin();
assign_min(v, u, assignments);
}
}
Dinic run_flow() {
int source = 1, sink = 2;
int last = 3;
for (auto query : queries) {
enumerate_assignments[query.z] = last++;
}
for (auto& itr : edges) {
enumerate_edges[itr] = last++;
}
Dinic dinic(last + 1);
for (auto& itr : enumerate_assignments) {
dinic.add_edge(source, itr.second, 1);
}
for (auto& itr : max_assignments) {
dinic.add_edge(enumerate_assignments[itr.second], enumerate_edges[itr.first], 1);
}
for (auto& itr : min_assignments) {
dinic.add_edge(enumerate_assignments[itr.second], enumerate_edges[itr.first], 1);
}
for (auto& itr : edges) {
dinic.add_edge(enumerate_edges[itr], sink, 1);
}
int flow = dinic.max_flow(source, sink);
return dinic;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
if (u > v) swap(u, v);
edges.push_back({u, v});
}
LCA lca(n + 1);
lca.init();
int q;
cin >> q;
while (q--) {
char type;
int u, v, z;
cin >> type >> u >> v >> z;
queries.push_back({type, u, v, z});
if (type == 'M') {
max_lcas[lca.lca(u, v)].push_back(z);
max_lcas[lca.lca(u, v)].push_back(z);
max_removals[u].push_back(z);
max_removals[v].push_back(z);
}
else {
min_lcas[lca.lca(u, v)].push_back(z);
min_lcas[lca.lca(u, v)].push_back(z);
min_removals[u].push_back(z);
min_removals[v].push_back(z);
}
}
multiset<int> temp_max;
multiset<int> temp_min;
assign_max(1, 0, temp_max);
assign_min(1, 0, temp_min);
Dinic dinic = run_flow();
set<pair<int, int>> full_edges = dinic.get_full_edges();
map<pair<int, int>, int> answer;
for (auto& itr : max_assignments) {
if (full_edges.count({enumerate_assignments[itr.second], enumerate_edges[itr.first]})) {
answer[itr.first] = itr.second;
}
}
for (auto& itr : min_assignments) {
if (full_edges.count({enumerate_assignments[itr.second], enumerate_edges[itr.first]})) {
answer[itr.first] = itr.second;
}
}
for (auto itr : edges) {
cout << itr.first << ' ' << itr.second << ' ';
if (answer.count(itr)) {
cout << answer[itr] << '\n';
}
else if (max_assignments.count(itr)) {
cout << max_assignments[itr] << '\n';
}
else if (min_assignments.count(itr)) {
cout << min_assignments[itr] << '\n';
}
else {
cout << 0 << '\n';
}
}
}
Compilation message
minmaxtree.cpp: In member function 'std::set<std::pair<long long int, long long int> > Dinic::get_full_edges()':
minmaxtree.cpp:136:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<Dinic::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int i = 0; i < G.size(); i++) {
| ~~^~~~~~~~~~
minmaxtree.cpp: In function 'Dinic run_flow()':
minmaxtree.cpp:233:9: warning: unused variable 'flow' [-Wunused-variable]
233 | int flow = dinic.max_flow(source, sink);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
382 ms |
82692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
320 ms |
74684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
