能互关吗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
inline char gc()
{
    static char buf[100001],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T> inline void read(T &x)
{
    T t=0,u=1;char c=gc();
    while(c<'0'||c>'9') {if(c=='-') u=-1; c=gc();}
    while(c>='0'&&c<='9') t*=10,t+=c-'0',c=gc();
    x=t*u;return;
}
const int N=1000001;
int n,fa[N];
ll f[N],g[N];
vector<int> a[N];
struct
{
    ll a,b,c;
}b[N];
struct str{
    int x;
    ll w;
    str() {}
    str(int x,ll w):x(x),w(w) {}
    friend bool operator<(str a,str b){
        return a.w>b.w;
    }
};
void dfs0(int x){
    for(auto i:a[x]){
        if(i==fa[x]) continue;
        fa[i]=x;
        dfs0(i);
    }
}
lll sum(int x,ll t1,ll t2)
{
    if(b[x].b+b[x].c*t2>=1)
    {
        return b[x].b*(t2-t1+1)+(lll)b[x].c*((t1+t2)*(t2-t1+1)>>1);
    }
    else
    {
        ll z=(1-b[x].b)/b[x].c;
        if(z<t1) return t2-t1+1;
        else return b[x].b*(z-t1+1)+(lll)b[x].c*((t1+z)*(z-t1+1)>>1)+(t2-z);
    }
}
void dfs(int x)
{
    g[x]=f[x];
    for(auto i:a[x])
    {
        dfs(i);
        g[x]=min(g[x],g[i]-1);
    }
}
bool check(ll t)
{
    for(int i=1;i<=n;++i)
    {
        ll l=1,r=t;
        while(l<r)
        {
            ll z=l+r+1>>1;
            if(sum(i,z,t)>=b[i].a) l=z;
            else r=z-1;
        }
        if(sum(i,l,t)<b[i].a) return false;
        f[i]=l;
    }
    dfs(1);
    priority_queue<str> Q;
    Q.emplace(1,g[1]);
    ll p=0;
    while(!Q.empty())
    {
        int x=Q.top().x;
        Q.pop();
        ++p;
        if(p>g[x]) return false;
        for(auto i:a[x]) Q.emplace(i,g[i]);
    }
    return true;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(b[i].a),read(b[i].b),read(b[i].c);
    }
    for(int i=1;i<=n-1;++i)
    {
        int x,y;
        read(x),read(y);
        a[x].emplace_back(y);
        a[y].emplace_back(x);
    }
    dfs0(1);
    for(int i=1;i<=n;++i)
    {
        vector<int> z;
        swap(z,a[i]);
        for(auto j:z) if(j!=fa[i]) a[i].emplace_back(j);
    }
    ll l=1,r=1e9;
    while(l<r)
    {
        ll z=l+r>>1;
        if(check(z)) r=z;
        else l=z+1;
    }
    printf("%lld",l);
    fclose(stdin);
    fclose(stdout);
    return 0;
}