#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=70010, inf=2e9, LG=18;
int n;
pii E[MX];
vector<int> G1[MX];
int nu[MX], ri[MX];
int sp[MX][LG], dep[MX];
void dfs1(int v, int p, int d=1){
static int now=0;
nu[v]=++now; ri[v]=nu[v]; dep[v]=d;
for(int i=1; i<LG; i++) sp[v][i]=sp[sp[v][i-1]][i-1];
for(int x:G1[v]) if(nu[x]==0) sp[x][0]=v, dfs1(x,v,d+1), ri[v]=max(ri[v], ri[x]);
}
void init_tree(){
cin>>n;
for(int i=1; i<n; i++){
int u,v; cin>>u>>v;
G1[u].push_back(v);
G1[v].push_back(u);
E[i]={u,v};
}
dfs1(1,-1);
}
int lca(int u, int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=LG-1; i>=0; i--)
if(dep[u]-(1<<i)>=dep[v]) u=sp[u][i];
if(u==v) return u;
for(int i=LG-1; i>=0; i--)
if(sp[u][i]!=sp[v][i]) u=sp[u][i], v=sp[v][i];
return sp[u][0];
}
struct query{
int v, p, z; bool ismx;
bool operator < (const query &q) const {
return nu[v]<nu[q.v];
}
};
query Q[2*MX];
int q;
int pl[MX], pr[MX];
struct seg_st{
pii tree1[1<<19];
int tree2[1<<19], tree3[1<<19];
void upt(int v, int s, int e, int pos){
if(pos<s || e<pos) return;
if(s==e){
query y=Q[s];
tree1[v]=pii(dep[y.p], s);
tree2[v]=(y.ismx ? y.z : inf);
tree3[v]=(y.ismx ? -1 : y.z);
return;
}
upt(v*2,s,(s+e)/2,pos);
upt(v*2+1,(s+e)/2+1,e,pos);
tree1[v]=max(tree1[v*2], tree1[v*2+1]);
tree2[v]=min(tree2[v*2], tree2[v*2+1]);
tree3[v]=max(tree3[v*2], tree3[v*2+1]);
}
void erase(int pos){
Q[pos]={0,0,-1,false};
upt(1,1,q,pos);
}
pii qu1(int v, int s, int e, int l, int r){
if(r<s || e<l) return pii(0,0);
if(l<=s && e<=r) return tree1[v];
return max(qu1(v*2,s,(s+e)/2,l,r), qu1(v*2+1,(s+e)/2+1,e,l,r));
}
pii qu1(int l, int r){
l=max(1,l); r=min(r,q);
if(r<l) return pii(0,0);
return qu1(1,1,q,l,r);
}
int mx(int v, int s, int e, int l, int r){
if(r<s || e<l) return inf;
if(l<=s && e<=r) return tree2[v];
return min(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
}
int mx(int l, int r){
if(r<l) return inf;
return mx(1,1,q,l,r);
}
int mn(int v, int s, int e, int l, int r){
if(r<s || e<l) return -1;
if(l<=s && e<=r) return tree3[v];
return max(mn(v*2,s,(s+e)/2,l,r), mn(v*2+1,(s+e)/2+1,e,l,r));
}
int mn(int l, int r){
if(r<l) return -1;
return mn(1,1,q,l,r);
}
} Seg;
void init_seg(){
for(int i=1; i<=q; i++) Seg.upt(1,1,q,i);
}
void init_query(){
int k; cin>>k;
for(int i=1; i<=k; i++){
char x; int u,v,z; cin>>x>>u>>v>>z;
if(dep[u]<dep[v]) swap(u,v);
int p=lca(u,v);
if(v==p) Q[++q]={u,p,z,x=='M'};
else Q[++q]={u,p,z,x=='M'}, Q[++q]={v,p,z,x=='M'};
}
sort(Q+1, Q+q+1);
int re[MX];
for(int i=1; i<=n; i++) re[nu[i]]=i;
for(int i=1; i<=n; i++){
query tmp={re[i],0,0,0};
pl[i]=lower_bound(Q+1, Q+q+1, tmp)-Q;
pr[i]=upper_bound(Q+1, Q+q+1, tmp)-Q-1;
}
// for(int i=1; i<=q; i++) cout<<Q[i].v<<' '<<Q[i].p<<' '<<Q[i].z<<'\n';
init_seg();
}
struct edge {
int u, v, a, b;
};
vector<edge> F;
void dfs2(int v, int p){
for(int x:G1[v]){
if(x==p) continue;
dfs2(x,v);
int l=pl[nu[x]], r=pr[ri[x]];
pii now=Seg.qu1(l, r);
while(now.first>=dep[x]){
Seg.erase(now.second);
// cout<<"ERASED: "<<now.second<<'\n';
now=Seg.qu1(l, r);
}
int mx=Seg.mx(l,r), mn=Seg.mn(l,r);
F.push_back({x,v,mx,mn});
// cout<<"!!: "<<"["<<l<<", "<<r<<"]: "<<v<<' '<<x<<": "<<mx<<' '<<mn<<'\n';
}
}
vector<pii> G2[MX];
bool ans[MX];
bool vis[MX];
bool dfs3(int v, int pidx){
vis[v]=true;
bool outed=false;
for(pii &e:G2[v]){
int idx=e.second;
if(idx==pidx) continue;
int x=e.first;
// cout<<v<<" - "<<x<<'\n';
if(vis[x]) ans[idx]=true, outed=true;
else{
if(!dfs3(x,idx)) ans[idx]=false;
else ans[idx]=true, outed=true;
}
}
return outed;
}
void find_edge(){
dfs2(1,-1);
vector<int> Z;
for(int i=0; i<(int)F.size(); i++){
edge &e=F[i];
// cout<<e.u<<' '<<e.v<<": "<<e.a<<' '<<e.b<<'\n';
if(e.a==inf && e.b<0) { e.a=e.b=inf; continue; }
if(e.a==inf) e.a=e.b;
if(e.b<0) e.b=e.a;
Z.push_back(e.a);
Z.push_back(e.b);
}
sort(Z.begin(), Z.end());
Z.resize(unique(Z.begin(), Z.end())-Z.begin());
for(int i=0; i<(int)F.size(); i++){
edge &e=F[i];
int x=lower_bound(Z.begin(), Z.end(), e.a)-Z.begin()+1;
int y=lower_bound(Z.begin(), Z.end(), e.b)-Z.begin()+1;
G2[x].push_back({y, i});
G2[y].push_back({x, i});
}
for(int i=1; i<=(int)Z.size(); i++){
if(!vis[i]) dfs3(i,-1);
}
}
void show(){
for(int i=0; i<(int)F.size(); i++){
cout<<F[i].u<<' '<<F[i].v<<' '<<(ans[i] ? F[i].a : F[i].b)<<'\n';
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
init_tree();
init_query();
find_edge();
show();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
534 ms |
32364 KB |
Output is correct |
| 2 |
Correct |
461 ms |
32364 KB |
Output is correct |
| 3 |
Correct |
410 ms |
32364 KB |
Output is correct |
| 4 |
Correct |
397 ms |
34512 KB |
Output is correct |
| 5 |
Correct |
475 ms |
34512 KB |
Output is correct |
| 6 |
Correct |
431 ms |
34512 KB |
Output is correct |
| 7 |
Correct |
448 ms |
34512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
324 ms |
34512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
