#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define INF (int)1e18
auto pi = new char[10000000];
int ru() {
while (!isdigit(*pi)) {
pi++;
}
int res = 0;
while (isdigit(*pi)) {
res *= 10;
res += *pi - '0';
pi++;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef CB
freopen("be2.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
fread(pi,1,10000000,stdin);
int N=ru(),M=ru();
vector<int>v(N+1);
int su=0;
for(int i=1;i<=N;i++){
v[i]=ru();
v[i]=ru();
su+=v[i];
}
vector<vector<int>>g(N+1);
for(int i=0;i<M;i++){
int a=ru(),b=ru();
g[a].push_back(b);
g[b].push_back(a);
}
int ans=INF;
int ans1=0;
int ans2=0;
vector<int>l(N+1,INF),a(N+1,0);
vector<int>s(N+1);
vector<ordered_set<int>>z(N+1);
auto dfs=[&](auto self,int i)->void{
for(int j:g[i]){
if(l[j]==l[i]-1){
continue;
}
if(l[j]!=INF){
if(l[j]<l[a[i]]){
a[i]=j;
}
continue;
}
l[j]=l[i]+1;
self(self,j);
s[i]+=s[j];
if(l[a[j]]<l[a[i]]){
a[i]=a[j];
}
if(l[a[j]]>l[i]){
z[j].insert(s[j]);
int s1=su-s[j],s2,s3;
auto f=[&](){
ans1=max({s1,s2,s3})-min({s1,s2,s3});
if(ans1<ans){
ans=ans1;
ans2=0;
}
};
auto it=z[j].upper_bound(s[j]/2);
if(it!=z[j].end()){
s2=*it;
s3=su-s1-s2;
f();
}
if(it!=z[j].begin()){
--it;
s2=*it;
s3=su-s1-s2;
f();
}
if(!z[j].empty()){
s2=*s.begin();
s3=su-s1-s2;
f();
s2=*--s.end();
s3=su-s1-s2;
f();
}
int ll=max({s1-ans,su-s1-(s1+ans),(su-s1-ans)/2});
int hh=min({s1+ans,su-s1-(s1-ans),(su-s1+ans)/2});
if(ll<=hh){
ans2+=z[j].order_of_key(hh+1)-z[j].order_of_key(ll);
}
}
if(z[j].size()>z[i].size()){
swap(z[i],z[j]);
}
int x=-1,xx=0;
for(int s1:z[j]){
if(s1==x){
ans2+=xx;
continue;
}
x=s1;
xx=0;
int s2,s3;
auto f=[&](){
ans1=max({s1,s2,s3})-min({s1,s2,s3});
if(ans1<ans){
ans=ans1;
ans2=0;
}
};
auto it=z[i].upper_bound(s[i]/2);
if(it!=z[i].end()){
s2=*it;
s3=su-s1-s2;
f();
}
if(it!=z[i].begin()){
--it;
s2=*it;
s3=su-s1-s2;
f();
}
if(!z[i].empty()){
s2=*s.begin();
s3=su-s1-s2;
f();
s2=*--s.end();
s3=su-s1-s2;
f();
}
int ll=max({s1-ans,su-s1-(s1+ans),(su-s1-ans)/2});
int hh=min({s1+ans,su-s1-(s1-ans),(su-s1+ans)/2});
if(ll<=hh){
ans2+=xx=z[i].order_of_key(hh+1)-z[i].order_of_key(ll);
}
}
for(int k:z[j]){
z[i].insert(k);
}
}
s[i]+=v[i];
};
l[1]=0;
dfs(dfs,1);
cout<<ans<<'\n';
cout<<ans2<<'\n';
return 0;
}
Compilation error
exit status 1
main.cpp: In function 'int main()':
main.cpp:57:22: error: use of 'auto' in lambda parameter declaration only available with '-std=c++14' or '-std=gnu++14'
57 | auto dfs=[&](auto self,int i)->void{
| ^~~~
main.cpp: In lambda function:
main.cpp:69:29: error: 'self' cannot be used as a function
69 | self(self,j);
| ~~~~^~~~~~~~
main.cpp: In function 'int main()':
main.cpp:162:12: error: no match for call to '(main()::<lambda(int, long long int)>) (main()::<lambda(int, long long int)>&, int)'
162 | dfs(dfs,1);
| ~~~^~~~~~~
main.cpp:57:18: note: candidate: 'main()::<lambda(int, long long int)>'
57 | auto dfs=[&](auto self,int i)->void{
| ^
main.cpp:57:18: note: no known conversion for argument 1 from 'main()::<lambda(int, long long int)>' to 'int'
main.cpp:36:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attri...