#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
vector<pair<int, int>> rasps;
int cn;
struct Dinic {
int n;
struct EDGE {
int from, to, cap, prev;
};
vector<EDGE> edges;
vector<int> dist, last, fakeLast;
Dinic (int _n) {
n = _n + 1;
last.resize(n, -1);
dist.resize(n);
}
void addEdge(int u, int v, int c) {
edges.push_back({u, v, c, last[u]});
last[u] = edges.size() - 1;
edges.push_back({v, u, 0, last[v]});
last[v] = edges.size() - 1;
}
bool bfs(int s, int d) {
dist.assign(n, inf);
queue<int> q;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = last[x]; i != -1; i = edges[i].prev) {
if (edges[i].cap && dist[edges[i].to] == inf) {
dist[edges[i].to] = dist[x] + 1;
q.push(edges[i].to);
}
}
}
fakeLast = last;
return dist[d] != inf;
}
int dfs(int nod, int d, int push) {
if (push == 0)
return 0;
if (nod == d)
return push;
int ans = 0;
for (int i = fakeLast[nod]; i != -1; i = edges[i].prev) {
if (push == 0)
break;
fakeLast[nod] = i;
if (dist[edges[i].to] > dist[nod] && edges[i].cap) {
int x = dfs(edges[i].to, d, min(push, edges[i].cap));
push -= x;
ans += x;
edges[i].cap -= x;
edges[i ^ 1].cap += x;
}
}
return ans;
}
int maxFlow(int s, int d) {
int ans = 0;
while (bfs(s, d))
ans += dfs(s, d, inf);
return ans;
}
void skib(int s, int d) {
maxFlow(s, d);
for (int i = 0; i < (int)edges.size(); i += 2)
if (2 <= edges[i].to && edges[i].to <= cn && edges[i].cap == 0)
rasps.push_back({edges[i].to, edges[i].from});
}
};
const int N = 70005;
vector<int> vec[N];
vector<int> lazyMare[N], lazyMic[N];
set<int> setMare[N], setMic[N];
int lift[20][N], depth[N], mare[N], mic[N];
void dfs(int nod, int papa) {
depth[nod] = 1 + depth[papa];
lift[0][nod] = papa;
for (int bit = 1; bit < 20; bit ++)
lift[bit][nod] = lift[bit - 1][lift[bit - 1][nod]];
for (auto i : vec[nod])
if (i != papa)
dfs(i, nod);
}
int lca(int x, int y) {
if (depth[x] > depth[y])
swap(x, y);
for (int bit = 19; bit >= 0; bit --)
if (depth[lift[bit][y]] >= x)
y = lift[bit][y];
if (x == y)
return x;
for (int bit = 19; bit >= 0; bit --)
if (lift[bit][x] != lift[bit][y]) {
x = lift[bit][x];
y = lift[bit][y];
}
return lift[0][x];
}
void dfsMare(int nod, int papa) {
int fmax = 0;
for (auto i : vec[nod]) {
if (i == papa)
continue;
dfsMare(i, nod);
if (setMare[i].size() >= setMare[fmax].size())
fmax = i;
}
swap(setMare[fmax], setMare[nod]);
for (auto i : vec[nod]) {
if (i == papa)
continue;
for (auto j : setMare[i])
setMare[nod].insert(j);
setMare[i].clear();
}
for (auto i : lazyMare[nod]) {
if (i < 0)
setMare[nod].erase(-i);
else
setMare[nod].insert(i);
}
if (setMare[nod].empty())
mare[nod] = -1;
else
mare[nod] = *setMare[nod].rbegin();
}
void dfsMic(int nod, int papa) {
int fmax = 0;
for (auto i : vec[nod]) {
if (i == papa)
continue;
dfsMic(i, nod);
if (setMic[i].size() >= setMic[fmax].size())
fmax = i;
}
swap(setMic[fmax], setMic[nod]);
for (auto i : vec[nod]) {
if (i == papa)
continue;
for (auto j : setMic[i])
setMic[nod].insert(j);
setMic[i].clear();
}
for (auto i : lazyMic[nod]) {
if (i < 0)
setMic[nod].erase(-i);
else
setMic[nod].insert(i);
}
if (setMic[nod].empty())
mic[nod] = -1;
else
mic[nod] = *setMic[nod].begin();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
cn = n;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 0);
int q;
cin >> q;
while (q --) {
char ch;
int x, y, z;
cin >> ch >> x >> y >> z;
if (ch == 'M') {
lazyMare[x].push_back(z);
lazyMare[y].push_back(z);
lazyMare[lca(x, y)].push_back(-z);
} else {
lazyMic[x].push_back(z);
lazyMic[y].push_back(z);
lazyMic[lca(x, y)].push_back(-z);
}
}
dfsMare(1, 0);
/*dfsMic(1, 0);
map<int, int> mp, remp;
int cnt = n;
Dinic ds(3 * n + 2);
for (int i = 2; i <= n; i ++) {
if (mare[i] != -1 && mp[mare[i]] == 0) {
mp[mare[i]] = ++cnt;
remp[cnt] = mare[i];
ds.addEdge(0, mp[mare[i]], 1);
}
if (mic[i] != -1 && mp[mic[i]] == 0) {
mp[mic[i]] = ++cnt;
remp[cnt] = mic[i];
ds.addEdge(0, mp[mic[i]], 1);
}
}
for (int i = 2; i <= n; i ++) {
if (mare[i] != -1)
ds.addEdge(mp[mare[i]], i, 1);
if (mic[i] != -1)
ds.addEdge(mp[mic[i]], i, 1);
ds.addEdge(i, 1, 1);
}
ds.skib(0, 1);
vector<int> ans(n + 1, -1);
for (auto i : rasps)
ans[i.first] = remp[i.second];
for (int i = 2; i <= n; i ++) {
if (ans[i] == -1) {
if (mic[i] != -1)
ans[i] = mic[i];
else if (mare[i] != -1)
ans[i] = mare[i];
else
ans[i] = 69;
}fds
}*/
for (int i = 2; i <= n; i ++)
cout << i << " " << lift[0][i] << " " << (mare[i] == -1 ? 69 : mare[i]) << '\n';
}
# | 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... |