Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <math.h>
- #include <vector>
- #include <set>
- #include <unordered_set>
- #include <tuple>
- #include <map>
- #include <unordered_map>
- #include <string>
- #include <string.h>
- #include <utility>
- #include <algorithm>
- #include <queue>
- #include <deque>
- #include <iterator>
- #include <stdlib.h>
- #include <cstdlib>
- #include <bitset>
- #include <fstream>
- #include <iomanip>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef vector<int> vi;
- typedef vector<ll> vill;
- typedef vector<vi> vvi;
- typedef vector<vill> vvill;
- typedef pair<int, int> pii;
- #define rall(a) a.rbegin(), a.rend()
- #define all(a) a.begin(), a.end()
- #define pb push_back
- #define pf push_front
- #define fi first
- #define se second
- #define forn(i, x) for (int i = 0; i < x; ++i)
- #define for1(i, x) for (int i = 1; i < x; ++i)
- using namespace std;
- vvi g;
- vi lamp;
- vi dpl;
- vi dpr;
- vi p;
- vector<bool> marker;
- int dfs (int v) {
- marker[v] = 1;
- for (int i = 0; i < g[v].size(); ++i) {
- int to = g[v][i];
- if (!marker[to]) {
- p[to] = v;
- dpl[to] += dpl[v];
- dpr[v] += dfs(to) + lamp[to];
- }
- }
- return dpr[v];
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n = 0; cin >> n;
- marker.assign(n, false);
- g.resize(n);
- dpl.resize(n);
- dpr.resize(n);
- lamp.resize(n);
- p.resize(n);
- int start = 0;
- for (int i = 0; i < n; ++i) {
- int tmp, cost; cin >> tmp >> cost;
- --tmp;
- if (tmp != -1) {
- g[i].pb(tmp);
- g[tmp].pb(i);
- }
- lamp[i] = cost;
- // dpl[i] = cost;
- }
- dpl[0] = lamp[0];
- // dpr[start] = dfs(start) - lamp[v];
- dfs(start);
- cout << endl;
- for (int i = 0; i < n; ++i) {
- cout << i + 1 << " ";
- cout << dpl[i] << " " << dpr[i] << endl;
- }
- int ans = 0;
- vector<int> answer;
- for (int i = 1; i < n && ans < 2; ++i) {
- if (dpl[i] * 2 == dpr[i] || dpr[i] * 2 == dpl[i]) {
- answer.pb(i + 1);
- ans++;
- }
- }
- if (ans < 2) {
- cout << -1;
- } else {
- cout << answer[0] << " " << answer[1];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement