1904D1 - Set To Max (Easy Version)/1904D2 - Set To Max (Hard Version)
Editorial 1:
Editorial 2:
<spoiler summary="Solution> Let's build a segtree/sparse table where each node stores the diameter (as a pair of nodes) for the nodes with $$$in$$$ values in the range $$$[l, r]$$$. To merge two diameters, we can enumerate all $$$4 \choose 2$$$ ways to pick the new diameter and take the best one.
To answer a query, we can first generate a list of banned intervals (just like solution 1) and use that list to generate the list of unbanned intervals. Then we can query our segtree for the diameter of each of ranges. Finally, we can combine the answers of the seperate queries to obtain the diameter of the connected subgraph. We know the farthest node from node $$$x$$$ is one of the two endpoints, so it suffices to just manually check the distance of those two nodes.
Final complexity is $$$O(n \log^2 n + \sum k \log n)$$$.
#include <bits/stdc++.h>
#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
const int MX = 2e5 +10, int_max = 0x3f3f3f3f;
using namespace std;
//lca template start
vector<int> dep, sz, par, head, tin, tout, tour;
vector<vector<int>> adj;
int n, ind, q;
void dfs(int x, int p){
sz[x] = 1;
dep[x] = dep[p] + 1;
par[x] = p;
for(auto &i : adj[x]){
if(i == p) continue;
dfs(i, x);
sz[x] += sz[i];
if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i);
}
if(p != 0) adj[x].erase(find(all(adj[x]), p));
}
void dfs2(int x, int p){
tour[ind] = x;
tin[x] = ind++;
for(auto &i : adj[x]){
if(i == p) continue;
head[i] = (i == adj[x][0] ? head[x] : i);
dfs2(i, x);
}
tout[x] = ind;
}
int k_up(int u, int k){
if(dep[u] <= k) return -1;
while(k > dep[u] - dep[head[u]]){
k -= dep[u] - dep[head[u]] + 1;
u = par[head[u]];
}
return tour[tin[u] - k];
}
int lca(int a, int b){
while(head[a] != head[b]){
if(dep[head[a]] > dep[head[b]]) swap(a, b);
b = par[head[b]];
}
if(dep[a] > dep[b]) swap(a, b);
return a;
}
int dist(int a, int b){
return dep[a] + dep[b] - 2*dep[lca(a, b)];
}
//lca template end
//segtree template start
#define ff first
#define ss second
int dist(pair<int, int> a){
return dist(a.ff, a.ss);
}
pair<int, int> merge(pair<int, int> a, pair<int, int> b){
auto p = max(pair(dist(a), a), pair(dist(b), b));
for(auto x : {a.ff, a.ss}){
for(auto y : {b.ff, b.ss}){
if(x == 0 || y == 0) continue;
p = max(p, pair(dist(pair(x, y)), pair(x, y)));
}
}
return p.ss;
}
pair<int, int> mx[MX*4];
#define LC(k) (2*k)
#define RC(k) (2*k +1)
void update(int p, int v, int k, int L, int R){
if(L + 1 == R){
mx[k] = {tour[p], tour[p]};
return ;
}
int mid = (L + R)/2;
if(p < mid) update(p, v, LC(k), L, mid);
else update(p, v, RC(k), mid, R);
mx[k] = merge(mx[LC(k)], mx[RC(k)]);
}
void query(int qL, int qR, vector<pair<int, int>>& ret, int k, int L, int R){
if(qR <= L || R <= qL) return ;
if(qL <= L && R <= qR){
ret.push_back(mx[k]);
return ;
}
int mid = (L + R)/2;
query(qL, qR, ret, LC(k), L, mid);
query(qL, qR, ret, RC(k), mid, R);
}
//segtree template end
int query(vector<int> arr, int x){
vector<pair<int, int>> banned, ret;
for(int u : arr){
if(lca(u, x) == u){
u = k_up(x, dep[x] - dep[u] - 1);
banned.push_back({0, tin[u]});
banned.push_back({tout[u], n});
}else{
banned.push_back({tin[u], tout[u]});
}
}
sort(all(banned), [&](pair<int, int> a, pair<int, int> b){
return (a.ff < b.ff) || (a.ff == b.ff && a.ss > b.ss);
});
vector<pair<int, int>> tbanned; //remove nested intervals
int mx = 0;
for(auto [a, b] : banned){
if(b <= mx) continue;
else if(a != b){
tbanned.pb({a, b});
mx = b;
}
}
banned = tbanned;
int tim = 0;
for(auto [a, b] : banned){
if(tim < a)
query(tim, a, ret, 1, 0, n);
tim = b;
}
if(tim < n)
query(tim, n, ret, 1, 0, n);
pair<int, int> dia = pair(x, x);
for(auto p : ret) dia = merge(dia, p);
int ans = max(dist(x, dia.ff), dist(x, dia.ss));
return ans;
}
void solve(){
cin >> n >> q;
dep = sz = par = head = tin = tout = tour = vector<int>(n+1, 0);
adj = vector<vector<int>>(n+1);
for(int i = 1; i<n; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0);
head[1] = 1;
dfs2(1, 0);
for(int i = 1; i<=n; i++){
update(tin[i], dep[i], 1, 0, n);
}
for(int i = 1; i<=q; i++){
int x, k;
cin >> x >> k;
vector<int> arr(k);
for(int& y : arr) cin >> y;
cout << query(arr, x) << "\n";
}
}
signed main(){
cin.tie(0) -> sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i<=T; i++){
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Can we represent the conditions as a graph?
Lets rewrite the condition that node $$$a$$$ must be smaller than node $$$b$$$ as a directed edge from $$$a$$$ to $$$b$$$. Then, we can assign each node a value based on the topological sort of this new directed graph. If this directed graph had a cycle, it is clear that there is no way to order the nodes.
With this in mind, we can try to construct a graph that would have these properties. Once we have the graph, we can topological sort to find the answer.
For now, let's consider the problem if it only had type 1 requirements (type 2 requirements can be done very similarly).
Thus, the problem reduces to "given a path and a node, add a directed edge from the node to every node in that path." To do this, we can use binary lifting. For each node, create $$$k$$$ dummy nodes, the $$$i$$$th of which represents the minimum number from the path between node $$$a$$$ and the $$$2^i$$$th parent of $$$a$$$. Now, we can draw a directed edge from the the $$$i$$$th dummy node of $$$a$$$ to the $$$i-1$$$th dummy node of $$$a$$$ and the $$$i-1$$$th dummy node of the $$$2^{i-1}$$$th parent of $$$a$$$.
Now, to add an edge from any node to a vertical path of the tree, we can repeatedly add an edge from that node to the largest node we can. This will add $$$O(\log n)$$$ edges per requirement.
The final complexity is $$$O((n+m)\log n)$$$ time and $$$O((n+m)\log n)$$$.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;
template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
inline ll ceil0(ll a, ll b) {
return a / b + ((a ^ b) > 0 && a % b);
}
void setIO() {
ios_base::sync_with_stdio(0); cin.tie(0);
}
const int MAXN = 200'000;
const int LG = 18;
const int MAXM = 200'000;
vector<int> g[MAXN + 5];
int sz[MAXN + 5], in[MAXN + 5], par[MAXN + 5], depth[MAXN + 5], head[MAXN + 5], tim;
int n, m;
void dfs1(int x, int p){
sz[x] = 1;
for(int &i : g[x]){
if(i == p) continue;
dfs1(i, x);
sz[x] += sz[i];
if(g[x][0] == p || sz[i] > sz[g[x][0]]) swap(g[x][0], i);
}
}
void dfs2(int x, int p){
in[x] = tim++;
par[x] = p;
depth[x] = depth[p] + 1;
for(int i : g[x]){
if(i == p) continue;
head[i] = (i == g[x][0] ? head[x] : i);
dfs2(i, x);
}
}
const int MAXSZ = MAXN + 2*MAXN*LG;
int down[LG][MAXN + 5];
int up[LG][MAXN + 5];
vector<int> dag[MAXSZ+ 5];
int lg[MAXN + 5];
void upd(int l, int r, int x, int t){
if(l <= in[x] && in[x] <= r){
if(l < in[x]) upd(l, in[x] - 1, x, t);
if(in[x] < r) upd(in[x] + 1, r, x, t);
} else {
int sz = lg[r - l + 1];
if(t == 2){
dag[up[sz][l]].pb(x);
dag[up[sz][r - (1 << sz) + 1]].pb(x);
} else {
dag[x].pb(down[sz][l]);
dag[x].pb(down[sz][r - (1 << sz) + 1]);
}
}
}
//1 is down, 2 is up
void draw(int a, int b, int c, int t){
while(head[a] != head[b]){
if(depth[head[a]] > depth[head[b]]) swap(a, b);
upd(in[head[b]], in[b], c, t);
b = par[head[b]];
}
if(depth[a] > depth[b]) swap(a, b);
upd(in[a], in[b], c, t);
}
bool vis[MAXSZ + 5], stk[MAXSZ + 5];
vector<int> ord;
bool fail;
int ind;
void dfs3(int x){
if(fail) return;
vis[x] = stk[x] = true;
for(int i : dag[x]){
if(i == x) continue;
if(!vis[i]){
dfs3(i);
} else if(stk[i]){
fail = true;
break;
}
}
stk[x] = false;
if(x <= n) ord.pb(x);
}
int main(){
setIO();
cin >> n >> m;
lg[1] = 0;
for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
tim = 0;
dfs1(1, 1);
head[1] = 1;
dfs2(1, 1);
for(int i = 1; i <= n; i++) down[0][in[i]] = up[0][in[i]] = i;
ind = n + 1;
for(int i = 1; i < LG; i++){
for(int j = 0; j + (1 << i) <= n; j++){
down[i][j] = ind++;
up[i][j] = ind++;
dag[down[i][j]].pb(down[i - 1][j]);
dag[down[i][j]].pb(down[i - 1][j + (1 << (i - 1))]);
dag[up[i - 1][j]].pb(up[i][j]);
dag[up[i - 1][j + (1 << (i - 1))]].pb(up[i][j]);
}
}
for(int i = 0; i < m; i++){
int t, a, b, c;
cin >> t >> a >> b >> c;
draw(a, b, c, t);
}
fail = false;
for(int i = 1; i <= n; i++){
if(!vis[i]){
dfs3(i);
if(fail) break;
}
}
if(fail){
cout << -1 << endl;
return 0;
}
reverse(ord.begin(), ord.end());
int ans[n + 1];
for(int i = 0; i < ord.size(); i++){
ans[ord[i]] = i + 1;
}
for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
}