#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef unsigned long long ull;
int n,m,ans,cnt;
struct node{
__int128 x,y;
}t[400005];
vector<int> ve[400005];
void dfs(int x,int p,int q){
if(ve[x].size()0){
// cout<<x<<endl;
// cout<<t[x].x<<" "<<t[x].y<<" "<<x<<endl;
t[x].x=t[x].xq+pt[x].y;
t[x].y=t[x].y*q;
__int128 powe=__gcd(t[x].x,t[x].y);
if(powe0) return;
t[x].x/=powe;
t[x].y/=powe;
// cout<<p<<" "<<q<<endl;
// cout<<t[x].x<<" "<<t[x].y<<" "<<x<<endl;
// cout<<"---------------"<<endl;
return ;
}
for(int i=0;i<ve[x].size();i++){
dfs(ve[x][i],p,q*ve[x].size());
}
}
void print(__int128 x)
{
if(x < 0)
{
x = -x;
putchar('-');
}
if(x > 9) print(x/10);
putchar(x%10 + '0');
}
int main() {
// std::ios::sync_with_stdio(false);
}
