#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
const int MAXN = 7e4+5;
const int INF = 1e9 + 15092007;
struct Query{
bool type; // ! 0/1 m/M
int u,v;
long long w;
Query(char x='#',int U=0,int V=0,long long W=0){
type = (x=='M' ? 1 : 0);
u=U;
v=V;
w=W;
}
};
int n,q;
vector<int> graph[MAXN];
vector<Query> query;
map<int,int> queryID;
int uID[MAXN],vID[MAXN];
struct Hopcorft{
int nL,nR;
vector<vector<int>> graph;
vector<int> matchLeft,matchRight;
vector<int> distancia;
queue<int> qu;
Hopcorft(int l,int r): nL(l),nR(r){
graph.resize(nL+1);
matchLeft.assign(nL+1,0);
matchRight.assign(nR+1,0);
distancia.assign(nL+1,0);
}
void addEdge(int u,int v){
graph[u].push_back(v);
}
bool bfs(){
for (int u=1;u<=nL;u++){
if (!matchLeft[u]){
distancia[u]=0;
qu.push(u);
} else distancia[u] = INF;
}
distancia[0]=INF;
while (!qu.empty()){
int u = qu.front(); qu.pop();
if (distancia[u]>=distancia[0]) continue;
for (int v :graph[u]){
if (distancia[matchRight[v]]==INF){
distancia[matchRight[v]] = distancia[u] + 1;
qu.push(matchRight[v]);
}
}
}
return (distancia[0]!=INF);
}
bool dfs(int u){
if (!u) return true;
for (int v : graph[u]){
if (distancia[matchRight[v]]==distancia[u]+1 and dfs(matchRight[v])){
matchRight[v] = u;
matchLeft[u] = v;
return true;
}
}
distancia[u] = INF;
return false;
}
int maxMatching(){
int match=0;
while (bfs()){
for (int u=1;u<=nL;u++){
if (!matchLeft[u] and dfs(u)) match++;
}
}
return match;
}
void getW(vector<int> &res){
maxMatching();
for (int u=1;u<=nL;u++){
if (matchLeft[u]) res[matchLeft[u]] = query[u].w;
}
}
};
// ! Sweepline part
vector<pair<int,int>> eventA[MAXN], eventR[MAXN];
inline void rangeAddEvent(int l,int r,int w,int type){
if (l>r) return;
eventA[l].emplace_back(w,type);
eventR[r].emplace_back(w,type);
}
// ! HLD
int timedfs=1, curChain=1,edgecnt=0;
int eID[MAXN]; // ! edge: parent[u] - u
int parent[MAXN];
int pos[MAXN],arr[MAXN];
namespace HeavyLight{
vector<int> chainHead,chainID;
vector<int> depth,sz;
void dfs(int u,int pre){
parent[u] = pre;
for (int v:graph[u]){
if (v^pre){
depth[v] = depth[u] + 1;
dfs(v,u);
sz[u] += sz[v];
}
}
}
void HLD(int u,int pre){
if (!chainHead[curChain]){
chainHead[curChain] = u;
}
chainID[u] = curChain;
pos[u] = timedfs;
arr[timedfs] = u;
timedfs++;
if (u==pre) eID[u] = 0;
else {
eID[u] = ++edgecnt;
}
int nxt=0;
for (int v:graph[u]){
if (v^pre){
if (!nxt and sz[v]>sz[nxt]){
nxt = v;
}
}
}
if (nxt) HLD(nxt,u);
for (int v:graph[u]){
if (v^pre and v^nxt){
curChain++;
HLD(v,u);
}
}
}
void addEvent(int u,int v,int w,int type){
while (chainHead[chainID[u]] != chainHead[chainID[v]]){
if (depth[chainHead[chainID[u]]] < depth[chainHead[chainID[v]]]) swap(u,v);
rangeAddEvent(pos[chainHead[chainID[u]]],u,w,type);
u = parent[chainHead[chainID[u]]];
}
if (depth[u] < depth[v]) swap(u,v);
if (u^v) rangeAddEvent(pos[v]+1, pos[u],w,type);
}
void initHLD(){
chainHead.assign(n+1,0);
chainID.assign(n+1,0);
depth.assign(n+1,0);
sz.assign(n+1,1);
dfs(1,1);
HLD(1,1);
}
};
using namespace HeavyLight;
void init(){
cin>>n;
for (int i=1;i<n;i++){
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
uID[i] = u;
vID[i] = v;
}
cin>>q;
query.resize(q+1);
for (int i=1;i<=q;i++){
char c;
int u,v,w;
cin>>c>>u>>v>>w;
query[i] = Query(c,u,v,w);
queryID[w] = i;
}
}
void sol(){
initHLD();
for (int i=1;i<=q;i++) addEvent(query[i].u,query[i].v,query[i].w,query[i].type);
vector<int> maxOfMin(n,-INF), minOfMax(n,INF);
multiset<int> activeMin,activeMax;
for (int curtime=1;curtime<=n;curtime++){
// ! start sweeping
for (pair<int,int> ev : eventA[curtime]){
if (ev.second) activeMax.insert(ev.first);
else activeMin.insert(ev.first);
}
int u = arr[curtime];
int e = eID[u];
if (e){
if (!activeMax.empty()) minimize(minOfMax[e],*activeMax.rbegin());
if (!activeMin.empty()) maximize(maxOfMin[e],*activeMin.begin());
}
for (pair<int,int> ev: eventR[curtime]){
if (ev.second){
multiset<int>::iterator it = activeMax.find(ev.first);
if (it!=activeMax.end()) activeMax.erase(it);
} else{
multiset<int>::iterator it = activeMin.find(ev.first);
if (it!=activeMin.end()) activeMin.erase(it);
}
}
}
Hopcorft karp(q,n-1);
for (int e=1;e<n;e++){
if (maxOfMin[e]!=-INF){
map<int,int>::iterator it = queryID.find(maxOfMin[e]);
karp.addEdge((*it).second,e);
}
if (minOfMax[e]!=INF and minOfMax[e]!=maxOfMin[e]){
map<int,int>::iterator it = queryID.find(minOfMax[e]);
karp.addEdge((*it).second,e);
}
}
vector<int> res(n,0);
for (int e=1;e<n;e++){
int val = 0;
maximize(val,maxOfMin[e]);
minimize(val,minOfMax[e]);
res[e] = val;
}
karp.getW(res);
map<pair<int,int>,int> toEID;
function<pair<int,int>(int,int)> uv = [&] (int u,int v) -> pair<int,int> {
if (u>v) swap(u,v);
return make_pair(u,v);
};
for (int v=2;v<=n;v++){
int u = parent[v];
toEID[uv(u,v)] = eID[v];
}
for (int e=1;e<n;e++){
int u = uID[e];
int v = vID[e];
cout<<u<<" "<<v<<" "<<res[toEID[uv(u,v)]]<<el;
}
}
int main(){
setup();
init();
sol();
}
Compilation message (stderr)
minmaxtree.cpp: In function 'void setup()':
minmaxtree.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen(FNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(FNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |