767C - Garland - CodeForces Solution

'''
https://codeforces.com/problemset/problem/767/C

输入 n(3≤n≤1e6)，表示一颗有 n 个节点的有根树，节点编号从 1 开始。
每行输入两个数，表示当前节点的父节点编号（如果是 0 表示当前节点是根节点），以及节点的点权，范围在 [-100,100]。
例如节点 1 的父节点为 2，则表示一条 2->1 的边。

你需要删除两条边，将这棵树分成三个连通块，且每个连通块的点权和相等。
假设删除的边是 a->b 和 c->d，你需要输出 b 和 d。如果有多种方案，输出任意一种。
如果无法做到，输出 -1。

输入
6
2 4
0 5
4 2
2 1
1 1
4 2
输出 1 4
解释 见右图

输入
6
2 4
0 6
4 2
2 1
1 1
4 2
输出 -1
'''

from itertools import *
from collections import *
from math import *
from heapq import *
from functools import *
from bisect import *
from random import *
import random
import sys
import os
from io import BytesIO, IOBase
from copy import deepcopy
import threading

BUFSIZE = 4096


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


def I():
    return input()


def II():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(input().split())


def LII():
    return list(map(int, input().split()))


def GMI():
    return map(lambda x: int(x) - 1, input().split())


def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))


def PF(a):
    return [0] + list(accumulate(a))


def solve():
    n = II()
    g = defaultdict(list)
    s = 0
    nums = [0]
    root = -1
    for i in range(1, n + 1):
        u, v = MI()
        nums.append(v)
        s += v
        if u:
            g[u].append(i)
        else:
            root = i
    if s % 3 != 0:
        print(-1)
        return
    s //= 3

    def dfs(u):
        nonlocal a, b
        ps = nums[u]
        for v in g[u]:
            ps += dfs(v)

        if ps == s:
            if a == 0:
                a = u
            elif b == 0:
                b = u
            return 0
        return ps

    a, b = 0, 0
    dfs(root)

    if a and b:
        print(a, b)
        return
    print(-1)


def solve1():
    n = II()
    g = defaultdict(list)
    s = 0
    nums = [0]
    root = -1
    for i in range(1, n + 1):
        u, v = MI()
        nums.append(v)
        s += v
        if u:
            g[u].append(i)
        else:
            root = i
    if s % 3 != 0:
        print(-1)
        return
    s //= 3

    a, b = 0, 0
    q = deque([root])
    arr = []
    while q:
        arr.extend(q)
        for _ in range(len(q)):
            u = q.popleft()
            for v in g[u]:
                q.append(v)
    for u in arr[::-1]:
        for v in g[u]:
            nums[u] += nums[v]
        if nums[u] == s and u != root:
            nums[u] = 0
            if a == 0:
                a = u
            elif b == 0:
                b = u

        if a and b:
            print(a, b)
            return
    print(-1)


solve1()