#include <bits/stdc++.h>
using namespace std;
const int N = 7e4 + 5;
int n, k, a, b, z, ans[N], cnt[N], color[N];
char c;
vector<int> mn[N], mx[N], cycle, nodes;
map<int, int> mnmp[N], mxmp[N], cmprs, revcmprs;
vector<pair<int, int>> tree[N], graph[N];
pair<int, int> edges[N], edgerange[N], par[N];
struct Path{
char c;
int a, b, z;
};
Path paths[N];
void dfs(int v, int p){
cnt[v] = 1;
int maxn = -1;
for(auto e : tree[v]){
if(e.first != p){
dfs(e.first, v);
cnt[v] += cnt[e.first];
if(maxn == -1 || cnt[e.first] > cnt[maxn]) maxn = e.first;
if(!mnmp[e.first].empty() && !mxmp[e.first].empty()){
a = (*prev(mnmp[e.first].end())).first, b = (*mxmp[e.first].begin()).first;
graph[a].push_back({b, e.second});
graph[b].push_back({a, e.second});
edgerange[e.second] = {a, b};
}
else if(!mnmp[e.first].empty() && mxmp[e.first].empty()){
a = b = (*prev(mnmp[e.first].end())).first;
graph[a].push_back({b, e.second});
graph[b].push_back({a, e.second});
edgerange[e.second] = {a, b};
}
else if(mnmp[e.first].empty() && !mxmp[e.first].empty()){
a = b = (*mxmp[e.first].begin()).first;
graph[a].push_back({b, e.second});
graph[b].push_back({a, e.second});
edgerange[e.second] = {a, b};
}
else edgerange[e.second] = {1, 1};
}
}
if(maxn != -1) swap(mnmp[v], mnmp[maxn]), swap(mxmp[v], mxmp[maxn]);
for(auto x : mn[v]) if(++mnmp[v][x] == 2) mnmp[v].erase(x);
for(auto x : mx[v]) if(++mxmp[v][x] == 2) mxmp[v].erase(x);
for(auto e : tree[v]){
if(e.first != p && e.first != maxn){
for(auto x : mnmp[e.first]) if(mnmp[v][x.first] += x.second == 2) mnmp[v].erase(x.first);
for(auto x : mxmp[e.first]) if(++mxmp[v][x.first] += x.second == 2) mxmp[v].erase(x.first);
}
}
}
void dfs2(int v, int p){
color[v] = 1;
nodes.push_back(v);
for(auto e : graph[v]){
if(color[e.first] == 0) par[e.first] = {v, e.second}, dfs2(e.first, v);
else if(color[e.first] == 1 && cycle.empty()){
while(v != e.first){
ans[par[v].second] = v;
cycle.push_back(v);
v = par[v].first;
}
ans[e.second] = e.first;
cycle.push_back(e.first);
}
}
color[v] = 2;
}
void dfs3(int v){
color[v] = 2;
for(auto e : graph[v]){
if(color[e.first] == 0){
ans[e.second] = e.first;
dfs3(e.first);
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n - 1; i++){
cin >> edges[i].first >> edges[i].second;
tree[edges[i].first].push_back({edges[i].second, i});
tree[edges[i].second].push_back({edges[i].first, i});
}
cin >> k;
for(int i = 1; i <= k; i++){
cin >> c >> a >> b >> z;
paths[i] = {c, a, b, z};
cmprs[z] = 1;
}
int cur = 0;
for(auto &p : cmprs){
p.second = ++cur;
revcmprs[cur] = p.first;
}
for(int i = 1; i <= k; i++){
paths[i].z = cmprs[paths[i].z];
if(paths[i].c == 'M') mx[paths[i].a].push_back(paths[i].z), mx[paths[i].b].push_back(paths[i].z);
else if(paths[i].c == 'm') mn[paths[i].a].push_back(paths[i].z), mn[paths[i].b].push_back(paths[i].z);
}
dfs(1, 0);
for(int i = 1; i <= n; i++){
if(!color[i] && !graph[i].empty()){
cycle.clear(), nodes.clear();
dfs2(i, 0);
for(auto x : nodes) color[x] = 0;
for(auto x : cycle) color[x] = 2;
for(auto x : cycle){
dfs3(x);
}
}
}
for(int i = 1; i <= n - 1; i++){
if(ans[i] == 0) ans[i] = edgerange[i].first;
}
for(int i = 1; i <= n - 1; i++) ans[i] = revcmprs[ans[i]];
for(int i = 1; i <= n - 1; i++) cout << edges[i].first << " " << edges[i].second << " " << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
284 ms |
40264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
29276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
13612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
