#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; #if __has_include() #include using namespace atcoder; #endif using ll = long long; #define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i)) #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(x) begin(x), end(x) #define all(s) (s).begin(),(s).end() //#define rep2(i, m, n) for (int i = (m); i < (n); ++i) //#define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) #define rever(vec) reverse(vec.begin(), vec.end()) #define sor(vec) sort(vec.begin(), vec.end()) #define fi first #define se second #define pb push_back #define P pair #define REP(i, n) for (int i = 0; i < (n); ++i) #define in scanner.read_int() ll mod = 1000000007; ll solve(ll XT,ll n,ll m,vector u,vector v,vector s){ if(n==1) return XT; vector> E(n); vector> S(n); for (int i=0; i V(n); vector X(n); vector F(n); int cv = -1; long long ca, cb; function BT = [&](int c, int p, long long v, bool x) { if (F[c] && X[c] != x) { cv = c; ca = V[c]; cb = v; } if (F[c]) return; F[c] = true; V[c] = v; X[c] = x; for (int i=0; i<(int)E[c].size(); i++) if (E[c][i] != p) BT(E[c][i], c, S[c][i]-v, !x); }; BT(0, -1, 0LL, false); if (cv != -1) { if ((ca-cb)%2 != 0) { return 0; } F = vector(n); BT(cv, -1, (ca+cb)/2, false); } bool ok = true; bool bi = true; for (int i=0; i 0&&*max_element(V.begin(), V.end()) <= XT) { return 1; } else{ return 0; } } long long mn0 = XT; long long mn1 = 1; for (int i=0; i par; vector siz; UnionFind(ll sz_):par(sz_),siz(sz_,1ll){ for(int i=0;i>n>>m>>K; vector a(m),b(m),c(m); UnionFind T(n); for(int i=0;i>a[i]>>b[i]>>c[i]; a[i]--; b[i]--; T.merge(a[i],b[i]); } vector> p(n); for(int i=0;i> h(n); for(int i=0;i u,v,s; map M; for(int j=0;j