#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 7e4+10;
int idx[mxn],par[mxn],link_top[mxn],sz[mxn],dep[mxn],bs[mxn],cnt,ans[mxn];
vector<int> tree[mxn];
int N,Q;
map<int,int> mp,rmp;
set<int> used;
struct SEG{
int seg[mxn*4];
SEG(){
memset(seg,-1,sizeof(seg));
}
void push(int now){
if(seg[now] == -1)return;
seg[now*2+2] = seg[now*2+1] = seg[now];
seg[now] = -1;
return;
}
void modify(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
seg[now] = v;
return;
}
int mid = (l+r)>>1;
push(now);
if(mid>=s)modify(now*2+1,l,mid,s,e,v);
if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
}
int getval(int now,int l,int r,int p){
if(l == r||seg[now] != -1)return seg[now];
int mid = (l+r)>>1;
if(mid>=p)return getval(now*2+1,l,mid,p);
else return getval(now*2+2,mid+1,r,p);
}
};
SEG mx,mn;
vector<pair<int,pii>> mxv,mnv;
struct DINIC{
struct E{
int t,c,f;
E(){
t = c= f = 0;
}
E(int tt,int cc):t(tt),c(cc),f(0){}
};
vector<E> e;
vector<int> ptr,lvl;
queue<int> q;
vector<vector<int>> p;
DINIC(int n = 0){
ptr = lvl = vector<int>(n,0);
e.clear();
p = vector<vector<int>>(n);
}
void add_edge(int a,int b,int c,int d = 0){
p[a].push_back(e.size());
e.push_back(E(b,c));
p[b].push_back(e.size());
e.push_back(E(a,d));
return;
}
bool bfs(int s,int t){
fill(lvl.begin(),lvl.end(),-1);
q.push(s);
lvl[s] = 0;
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto &eid:p[now]){
int nxt = e[eid].t;
if(e[eid].f == e[eid].c||lvl[nxt] != -1)continue;
lvl[nxt] = lvl[now]+1;
q.push(nxt);
}
}
return lvl[t] != -1;
}
int dfs(int now,int t,int f){
if(now == t||!f)return f;
for(int &i = ptr[now];i<p[now].size();i++){
int eid = p[now][i];
if(e[eid].c == e[eid].f||lvl[e[eid].t] != lvl[now]+1)continue;
if(int re = dfs(e[eid].t,t,min(f,e[eid].c-e[eid].f))){
e[eid].f += re;
e[eid^1].f -= re;
return re;
}
}
return 0;
}
int flow(int s,int t){
int ans = 0;
while(bfs(s,t)){
fill(ptr.begin(),ptr.end(),0);
while(int re = dfs(s,t,INT_MAX))ans += re;
}
return ans;
}
void getans(){
for(int i = 0;i<e.size();i+=2){
if(e[i].f == e[i].c&&e[i].t>N&&e[i^1].t<=N){
ans[e[i^1].t] = rmp[e[i].t-N];
}
}
}
};
void dfs1(int now){
sz[now] = 1;
for(auto nxt:tree[now]){
if(nxt == par[now])continue;
par[nxt] = now;
dep[nxt] = dep[now]+1;
dfs1(nxt);
sz[now] += sz[nxt];
if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
}
return;
}
void dfs2(int now,int top){
link_top[now] = top;
idx[now] = ++cnt;
if(bs[now])dfs2(bs[now],top);
for(auto nxt:tree[now]){
if(nxt == par[now]||nxt == bs[now])continue;
dfs2(nxt,nxt);
}
return;
}
inline void calc(int a,int b,int w,SEG &segtree){
int ta = link_top[a],tb = link_top[b];
while(ta != tb){
if(dep[ta]<dep[tb]){
swap(a,b);
swap(ta,tb);
}
segtree.modify(0,1,N,idx[ta],idx[a],w);
a = par[ta];
ta = link_top[a];
}
if(idx[a]>idx[b])swap(a,b);
if(a != b)segtree.modify(0,1,N,idx[a]+1,idx[b],w);
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<N;i++){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs1(1);
dfs2(1,1);
mx.modify(0,1,N,1,N,INT_MAX);
mn.modify(0,1,N,1,N,0);
cin>>Q;
for(int i = 0;i<Q;i++){
char c;
int a,b,w;
cin>>c>>a>>b>>w;
used.insert(w);
if(c == 'M')mxv.push_back({w,{a,b}});
else mnv.push_back({w,{a,b}});
}
sort(mxv.rbegin(),mxv.rend());
sort(mnv.begin(),mnv.end());
for(auto &i:mxv)calc(i.sc.fs,i.sc.sc,i.fs,mx);
for(auto &i:mnv)calc(i.sc.fs,i.sc.sc,i.fs,mn);
DINIC din(N*5+2);
for(int i = 2;i<=N;i++){
int low = mn.getval(0,1,N,idx[i]),high = mx.getval(0,1,N,idx[i]);
if(mp.find(low)==mp.end())mp[low] = mp.size()+1;
if(mp.find(high)==mp.end())mp[high] = mp.size()+1;
rmp[mp[low]] = low;
rmp[mp[high]] = high;
low = mp[low],high = mp[high];
//cout<<i<<':'<<low<<','<<high<<":"<<rmp[low]<<','<<rmp[high]<<endl;
if(used.find(rmp[low]) != used.end())din.add_edge(i,low+N,1);
if(used.find(rmp[high]) != used.end())din.add_edge(i,high+N,1);
din.add_edge(0,i,1);
//cout<<i<<endl;
}
for(auto &i:used)din.add_edge(mp[i]+N,N*5,1);
//cout<<"GRAPH MADE"<<endl;
/*
for(auto &i:rmp)cout<<i.fs<<':'<<i.sc<<',';cout<<endl;
for(int i = 0;i<din.e.size();i+=2){
cout<<din.e[i^1].t<<' '<<din.e[i].t<<endl;
}
*/
int tans = din.flow(0,N*5);
assert(tans == Q);
din.getans();
for(int i = 2;i<=N;i++){
cout<<par[i]<<' '<<i<<' '<<ans[i]<<'\n';
}
return 0;
}
Compilation message
minmaxtree.cpp: In member function 'int DINIC::dfs(int, int, int)':
minmaxtree.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int &i = ptr[now];i<p[now].size();i++){
| ~^~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'void DINIC::getans()':
minmaxtree.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DINIC::E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0;i<e.size();i+=2){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5148 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
249 ms |
44784 KB |
Output is correct |
| 2 |
Correct |
259 ms |
41928 KB |
Output is correct |
| 3 |
Correct |
222 ms |
41720 KB |
Output is correct |
| 4 |
Correct |
240 ms |
46916 KB |
Output is correct |
| 5 |
Correct |
224 ms |
41896 KB |
Output is correct |
| 6 |
Correct |
238 ms |
42348 KB |
Output is correct |
| 7 |
Correct |
225 ms |
41724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
34232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5148 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
249 ms |
44784 KB |
Output is correct |
| 6 |
Correct |
259 ms |
41928 KB |
Output is correct |
| 7 |
Correct |
222 ms |
41720 KB |
Output is correct |
| 8 |
Correct |
240 ms |
46916 KB |
Output is correct |
| 9 |
Correct |
224 ms |
41896 KB |
Output is correct |
| 10 |
Correct |
238 ms |
42348 KB |
Output is correct |
| 11 |
Correct |
225 ms |
41724 KB |
Output is correct |
| 12 |
Incorrect |
158 ms |
34232 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
