#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 70000;
const int MAX_K = 20;
int N, K;
string str;
vector<int> gp[MAX_N+1];
int p[MAX_N+1], up[MAX_N+1][MAX_K+1], lv[MAX_N+1];
bool vst[MAX_N+1];
struct Query{
int idx, x, y;
int d;
bool operator <(const Query &a)const{
return d<a.d;
}
};
vector<Query> qmx, qmn;
int lca(int x, int y){
for(int i=MAX_K-1; i>=0; i--){
if(lv[up[x][i]]>=lv[y]) x = up[x][i];
if(lv[up[y][i]]>=lv[x]) y = up[y][i];
}
if(x==y) return x;
for(int i=MAX_K-1; i>=0; i--){
if(up[x][i]!=up[y][i]){
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
void dfs(int x){
up[x][0] = p[x];
for(int i=1; i<MAX_K; i++){
up[x][i] = up[up[x][i-1]][i-1];
}
vst[x] = true;
for(int i : gp[x]){
if(!vst[i]){
p[i] = x; lv[i] = lv[x]+1;
dfs(i);
}
}
}
int mx[MAX_N+1], mn[MAX_N+1];
int g[MAX_N+1];
void ig(){
for(int i=1; i<=N; i++) g[i] = i;
}
int fg(int x){
return (x==g[x])?x:g[x] = fg(g[x]);
}
void ug(int x, int y){
x = fg(x); y = fg(y);
g[y] = x;
}
bool chk2[MAX_N+1];
bool chk[MAX_N+1];
vector<int> cost;
vector<pii> gp2[MAX_N+1];
set<int> st;
struct S{
int a, b, c;
};
vector<S> ans;
vector<int> vt;
int main(){
scanf("%d", &N);
for(int i=1; i<N; i++){
int a, b; scanf("%d%d", &a, &b);
gp[a].pb(b); gp[b].pb(a);
}
lv[1] = 1; dfs(1);
scanf("%d", &K);
for(int i=0; i<K; i++){
cin>>str;
int a, b, c; scanf("%d%d%d", &a, &b, &c);
if(str[0]=='M'){
qmx.pb({i, a, b, c});
}else{
qmn.pb({i, a, b, -c});
}
cost.pb(c);
st.insert(i);
}
sort(qmx.begin(), qmx.end()); sort(qmn.begin(), qmn.end());
ig();
for(int i=2; i<=N; i++) mx[i] = mn[i] = -1;
for(int i=0; i<qmx.size(); i++){
Query q = qmx[i];
int l = lca(q.x, q.y);
int nxt;
while(1){
q.x = fg(q.x);
if(lv[p[q.x]]>=lv[l]){
mx[q.x] = q.idx;
}else{
break;
}
ug(l, q.x);
q.x = p[q.x];
}
while(1){
q.y = fg(q.y);
if(lv[p[q.y]]>=lv[l]){
mx[q.y] = q.idx;
}else{
break;
}
ug(l, q.y);
q.y = p[q.y];
}
}
ig();
for(int i=0; i<qmn.size(); i++){
Query q = qmn[i];
int l = lca(q.x, q.y);
int nxt;
while(1){
q.x = fg(q.x);
if(lv[p[q.x]]>=lv[l]){
mn[q.x] = q.idx;
}else{
break;
}
ug(l, q.x);
q.x = p[q.x];
}
while(1){
q.y = fg(q.y);
if(lv[p[q.y]]>=lv[l]){
mn[q.y] = q.idx;
}else{
break;
}
ug(l, q.y);
q.y = p[q.y];
}
}
for(int i=2; i<=N; i++){
//cout<<mx[i]<<" "<<mn[i]<<endl;
if(mx[i]!=-1){
if(mn[i]!=-1){
gp2[mx[i]].pb({mn[i], i});
gp2[mn[i]].pb({mx[i], i});
}else{
if(!chk[mx[i]]){
chk[mx[i]] = true;
vt.pb(mx[i]);
chk2[i] = true;
ans.pb({i, p[i], cost[mx[i]]});
}
}
}else{
if(mn[i]!=-1){
if(!chk[mn[i]]){
chk[mn[i]] = true;
vt.pb({mn[i]});
chk2[i] = true;
ans.pb({i, p[i], cost[mn[i]]});
}
}
}
}
while(!st.empty()){
int t, k=-1;
if(vt.empty()){
t = (*st.begin());
k = gp2[t][0].first;
chk[t] = true;
ans.pb({gp2[t][0].second, p[gp2[t][0].second], cost[t]});
//cout<<t<<" "<<gp2[t][0].second<<" "<<p[gp2[t][0].second]<<endl;
chk2[gp2[t][0].second] = true;
}else{
t = vt.back(); vt.pop_back();
}
st.erase(t);
for(pii pr : gp2[t]){
if(!chk[pr.first] && pr.first!=k){
chk[pr.first] = true;
vt.pb(pr.first);
ans.pb({pr.second, p[pr.second], cost[pr.first]});
chk2[pr.second] = true;
}
}
}
for(int i=2; i<=N; i++){
if(!chk2[i]){
if(mn[i]!=-1){
ans.pb({i, p[i], mn[i]});
}else{
ans.pb({i, p[i], mx[i]});
}
}
}
if(ans.size()!=N-1){
while(1){
N--;
}
}
for(int i=0; i<ans.size(); i++){
printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<qmx.size(); i++){
~^~~~~~~~~~~
minmaxtree.cpp:120:7: warning: unused variable 'nxt' [-Wunused-variable]
int nxt;
^~~
minmaxtree.cpp:143:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<qmn.size(); i++){
~^~~~~~~~~~~
minmaxtree.cpp:146:7: warning: unused variable 'nxt' [-Wunused-variable]
int nxt;
^~~
minmaxtree.cpp:224:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size()!=N-1){
~~~~~~~~~~^~~~~
minmaxtree.cpp:229:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ans.size(); i++){
~^~~~~~~~~~~
minmaxtree.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
minmaxtree.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &K);
~~~~~^~~~~~~~~~
minmaxtree.cpp:105:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, c; scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
3576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
23860 KB |
Output is correct |
| 2 |
Correct |
210 ms |
21604 KB |
Output is correct |
| 3 |
Correct |
192 ms |
20448 KB |
Output is correct |
| 4 |
Correct |
220 ms |
24420 KB |
Output is correct |
| 5 |
Incorrect |
193 ms |
20456 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
16448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
3576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
