Untitled
unknown
plain_text
a month ago
2.0 kB
4
Indexable
#include <bits/stdc++.h> #include <unordered_map> #define Real_Madrid ios::sync_with_stdio(0);cin.tie(NULL); #define ceill(n, m) (n + m - 1) / m #define round(n, m) (n + m / 2) / m #define print(arr) for(auto _:arr)cout<<_<<" "; #define rall(a) a.rbegin(), a.rend() #define all(a) a.begin(), a.end() #define sz(s) (int)s.size() #define endl '\n' #define int long long typedef long long ll; typedef long double ld; using namespace std; //using u128 = __int128_t; const int N = 2e5 + 3, M = 2e5 + 5; const int mod = 2000000011; ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return (a / gcd(a, b) * b); } ll dx[] = { 0, 0, -1, 1, 1, 1, -1, -1 }; ll dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 }; int n, a[N], b[N]; vector<int>ans; vector<vector<int>>g; map<pair<int, int>, int>o; void DFS(int node, int p, int k) { a[node] = k; for (auto i : g[node]) { if (i == p) continue; DFS(i, node, k + (!b[o[{min(node, i), max(node, i)}]] ? -1 : 1)); a[node] = min(a[i], a[node]); } } void DFS2(int node, int p, int k) { for (auto i : g[node]) { if (i == p) continue; if (a[i] + k < 0 && !b[o[{min(node, i), max(node, i)}]]) ans.push_back(o[{min(node, i), max(node, i)}]), DFS2(i, node, k + 2); else DFS2(i, node, k); } } void Accepted() { cin >> n; g = vector<vector<int>>(n + 1); for (int i = 1; i < n; i++) { int u, v, s; cin >> u >> v >> s; if (u > v) swap(u, v); o[{u, v}] = i; b[i] = s; g[u].push_back(v); g[v].push_back(u); } DFS(1, -1, 0); DFS2(1, -1, 0); cout << ans.size() << endl; print(ans) } signed main() { Real_Madrid //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int t = 1; //cin >> t; while (t--) Accepted(); }
Editor is loading...
Leave a Comment