/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>
#define vvi vector <vector <int>>
#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll
#define fi first
#define se second
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
}
return false;
}
const int nmax = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
return uniform_int_distribution <long long>(l, r)(rng);
}
/** END OF TEMPLATE **/
int n, m, u, v, r[nmax];
pii edges[nmax];
vector <pii> adj[nmax];
int a[nmax], cnt = 1;
// LCA
int h[nmax], id[nmax];
int up[nmax][20];
void dfs(int u, int p) {
up[u][0] = (p == -1 ? u : p);
for (auto [v, w]: adj[u]) {
if (v == p) continue;
h[v] = h[u] + 1;
id[v] = w;
up[v][0] = u;
for (int j = 1; j < 20; ++j)
up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v, u);
}
}
int query_lca(int u, int v) {
if (h[u] != h[v]) {
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int j = 0; (1 << j) <= k; ++j)
if (k >> j & 1) u = up[u][j];
}
if (u == v) return u;
int k = __lg(h[u]);
for (int j = k; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
u = up[u][j], v = up[v][j];
}
}
return up[u][0];
}
// Dsu
int par[nmax];
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (h[x] > h[y]) swap(x, y);
par[y] = x;
}
bool check(int x, int y) {
return find(x) == find(y);
}
set <int> tmp;
void get(int u, int anc) {
if (check(u, anc)) return;
tmp.insert(id[u]);
unite(u, up[u][0]);
get(find(u), anc);
}
int main() {
synchronize;
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> edges[i].fi >> edges[i].se;
for (int i = 1; i < n; i++) {
cin >> r[i];
int idx = r[i];
auto [u, v] = edges[idx];
adj[u].emplace_back(v, idx);
adj[v].emplace_back(u, idx);
}
dfs(1, -1);
for (int i = 1; i <= n; i++) par[i] = i;
fill(a + 1, a + m + 1, -1);
for (int i = 1; i <= m; i++) {
if (a[i] != -1) continue;
auto [u, v] = edges[i];
if (check(u, v)) {
a[i] = cnt++;
continue;
}
tmp.clear();
int x = query_lca(u, v);
get(u, x); get(v, x);
tmp.erase(i);
for (int y: tmp) a[y] = cnt++;
a[i] = cnt++;
}
for (int i = 1; i <= m; i++) cout << a[i] << ' ';
return (0 ^ 0);
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |