#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 70005;
int n, m, dep[N], par[N], ans[N], piv;
bool vv[N], ve[N], on;
vector<int> tr[N], cyc, usd;
vector<pii> adj[N];
struct edge {
int a, b, x;
bool operator < (edge &T) {
return x < T.x;
}
} e[N];
struct coloring {
int c[N], p[N];
int Find (int X) {
if(p[X] == X) return X;
return p[X] = Find(p[X]);
}
void init () {
for(int i=1;i<=n;i++) {
c[i] = 0;
p[i] = i;
}
}
void color (int A, int B, int C) {
while(true) {
A = Find(A);
B = Find(B);
if(dep[A] == dep[B]) return;
if(dep[A] < dep[B]) swap(A, B);
c[A] = C;
p[A] = par[A];
}
}
} col[2];
void calc (int C, int P) {
dep[C] = dep[P] + 1;
par[C] = P;
for(auto &T : tr[C]) {
if(T == P) continue;
calc(T, C);
}
}
bool findcyc (int I) {
if(vv[I]) {
on = true;
piv = I;
return true;
}
vv[I] = true;
for(auto &T : adj[I]) {
int A, B;
tie(A, B) = T;
if(ve[B]) continue;
ve[B] = true;
if(findcyc(A)) {
if(on) {
cyc.push_back(I);
ans[B] = I;
}
else usd.push_back(I);
if(I == piv) on = false;
return true;
}
}
usd.push_back(I);
return false;
}
void dfs (int I) {
vv[I] = true;
for(auto &T : adj[I]) {
int A, B;
tie(A, B) = T;
if(vv[A]) continue;
ans[B] = A;
dfs(A);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++) {
int A, B;
scanf("%d%d",&A,&B);
tr[A].push_back(B);
tr[B].push_back(A);
}
calc(1, 0);
scanf("%d",&m);
for(int i=1;i<=m;i++) {
char typ[2];
scanf("%s%d%d%d",typ,&e[i].a,&e[i].b,&e[i].x);
if(typ[0] == 'm') e[i].x *= -1;
}
sort(e+1, e+1+m);
col[0].init();
col[1].init();
for(int i=1;i<=m;i++) {
col[e[i].x > 0].color(e[i].a, e[i].b, i);
}
for(int i=1;i<=n;i++) {
int A = col[0].c[i], B = col[1].c[i];
adj[A].push_back({B, i});
adj[B].push_back({A, i});
}
for(int i=0;i<=m;i++) {
if(vv[i]) continue;
findcyc(i);
for(auto &T : usd) {
vv[T] = false;
}
usd.clear();
for(auto &T : cyc) {
dfs(T);
}
cyc.clear();
}
for(int i=2;i<=n;i++) {
int T = 0;
if(ans[i]) T = ans[i];
else if(col[0].c[i]) T = col[0].c[i];
else if(col[1].c[i]) T = col[1].c[i];
printf("%d %d %d\n", par[i], i, abs(e[T].x));
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
minmaxtree.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A,&B);
~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
~~~~~^~~~~~~~~
minmaxtree.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d%d%d",typ,&e[i].a,&e[i].b,&e[i].x);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
14696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
14696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
