Untitled

 avatar
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