#include <bits/stdc++.h>
using namespace std;
const int mxN=7e4;
int n, ui, vi, d[mxN], anc[mxN][17], c1[mxN][17], c2[mxN][17], k, wi;
vector<int> adj[mxN];
char qt;
unordered_map<int, int> mp;
void dfs(int u=n-1, int p=-1) {
anc[u][0]=p;
for(int i=1; i<17; ++i)
anc[u][i]=anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1];
d[u]=p==-1?0:d[p]+1;
for(int v : adj[u])
if(v!=p)
dfs(v, u);
}
#define y(x) (2*(x))
#define n(x) (2*(x)+1)
struct twosat {
static const int mxN=3*(::mxN-1);
int n, c[2*mxN];
vector<int> a1[2*mxN], a2[2*mxN], st;
bool vis[2*mxN], ans[2*mxN];
void imp(int u, int v) {
a1[u].push_back(v);
a1[v^1].push_back(u^1);
}
void dfs1(int u) {
vis[u]=1;
for(int v : a1[u])
if(!vis[v])
dfs1(v);
st.push_back(u);
}
void dfs2(int u, int cu) {
vis[u]=0;
c[u]=cu;
for(int v : a2[u])
if(vis[v])
dfs2(v, cu);
}
bool ac() {
for(int i=0; i<2*n; ++i)
if(!vis[i])
dfs1(i);
for(int i=0; i<2*n; ++i)
for(int j : a1[i])
a2[j].push_back(i);
for(int i=n-1; i>=0; --i)
if(vis[st[i]])
dfs2(st[i], i);
for(int i=0; i<2*n; i+=2) {
if(c[i]==c[i^1])
return 0;
ans[i]=c[i]<c[i^1];
}
return 1;
}
} ts;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n-1; ++i) {
cin >> ui >> vi, --ui, --vi;
adj[ui].push_back(vi);
adj[vi].push_back(ui);
}
dfs();
memset(c2, 0x96, sizeof(c2));
cin >> k;
while(k--) {
cin >> qt >> ui >> vi >> wi, --ui, --vi;
int (*c)[17];
if(qt=='M') {
wi=-wi;
c=c2;
} else
c=c1;
if(d[ui]<d[vi])
swap(ui, vi);
auto ue=[&](int &u, int i) {
c[u][i]=max(wi, c[u][i]);
u=anc[u][i];
};
for(int i=16; i>=0; --i)
if(d[ui]-(1<<i)>=d[vi])
ue(ui, i);
if(ui!=vi) {
for(int i=16; i>=0; --i) {
if(anc[ui][i]!=anc[vi][i]) {
ue(ui, i);
ue(vi, i);
}
}
ue(ui, 0);
ue(vi, 0);
}
}
for(int i=16; i; --i) {
for(int j=0; j<n; ++j) {
c1[j][i-1]=max(c1[j][i], c1[j][i-1]);
c2[j][i-1]=max(c2[j][i], c2[j][i-1]);
if(anc[j][i-1]!=-1) {
c1[anc[j][i-1]][i-1]=max(c1[j][i], c1[anc[j][i-1]][i-1]);
c2[anc[j][i-1]][i-1]=max(c2[j][i], c2[anc[j][i-1]][i-1]);
}
}
}
for(int i=0; i<n-1; ++i) {
ts.imp(y(i), y(i+n-1));
if(mp.find(c1[i][0])!=mp.end())
ts.imp(y(mp[c1[i][0]]), y(i+n-1));
mp[c1[i][0]]=i+n-1;
c2[i][0]=-c2[i][0];
ts.imp(n(i), y(i+2*(n-1)));
if(mp.find(c2[i][0])!=mp.end())
ts.imp(y(mp[c2[i][0]]), y(i+2*(n-1)));
mp[c2[i][0]]=i+2*(n-1);
}
for(auto it=mp.begin(); it!=mp.end(); ++it)
if(1<=it->first&&it->first<=1e9)
ts.imp(n(it->second), y(it->second));
ts.ac();
for(int i=0; i<n-1; ++i)
cout << i+1 << " " << anc[i][0]+1 << " " << (ts.ans[y(i)]?c1[i][0]:c2[i][0]) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
26360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
57736 KB |
Output is correct |
| 2 |
Correct |
240 ms |
55532 KB |
Output is correct |
| 3 |
Correct |
237 ms |
57224 KB |
Output is correct |
| 4 |
Correct |
253 ms |
57868 KB |
Output is correct |
| 5 |
Correct |
304 ms |
56456 KB |
Output is correct |
| 6 |
Correct |
224 ms |
56496 KB |
Output is correct |
| 7 |
Correct |
246 ms |
55660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
54136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
26360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
