#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct trio{
ll suma, mindo;
int v;
};
trio make_trio(ll a, ll b, int c){
trio wyn;
wyn.suma=a; wyn.mindo=b; wyn.v=c;
return wyn;
}
const int N=1e5+50;
const ll I=1000LL*1000LL*1000LL*1000LL*1000LL*1000LL;
vector< pair<int, int> >Kra[N];
int Paliwo[N];
int Rozmiar[N];
int Ojciec[N];
int Odw[N];
int Zaz[N];
int Wynik[N];
vector< trio >Start[N];
vector<ll>Odleglosci;
void WczytajDane(int &n){
cin>>n; int a, b, c;
for(int i=1; i<=n; ++i) cin>>Paliwo[i];
for(int i=1; i<n; i++){
cin>>a>>b>>c;
Kra[a].push_back( make_pair(b, c) );
Kra[b].push_back( make_pair(a, c) );
}
}
void LiczRozmiar(int v){
Odw[v]=1; Rozmiar[v]++;
for(int i=0; i<(int)Kra[v].size(); i++){
if( Odw[ Kra[v][i].first ]==1 ) continue;
LiczRozmiar(Kra[v][i].first);
Ojciec[ Kra[v][i].first ]=v;
Rozmiar[v]+=Rozmiar[Kra[v][i].first];
}
}
int LiczCentroid(vector<int> &Aktu){
int v, czy, s; s=(int)Aktu.size();
for(int i=0; i<(int)Aktu.size(); i++){
v=Aktu[i];
czy=1;
for(int j=0; j<(int)Kra[v].size(); j++){
if( Ojciec[ v ]==Kra[v][j].first ) continue;
if( Rozmiar[ Kra[v][j].first ]>s/2 ) czy=0;
}
if( s-Rozmiar[v]>s/2 ) czy=0;
if( czy==1 ) return v;
}
return 0;
}
void LiczWynikWrzucOdleglosci(int v, int gdzie_wyn, ll suma, ll mini_od, ll mini_do, int k){
if(mini_do>=0LL) Wynik[gdzie_wyn]++;
//if( gdzie_wyn==5 ) cout << "dodaje do 5 " << v << " : " << mini_do << endl;
Odleglosci.push_back( mini_do ); Odw[v]=1;
ll mini, mini2;
if(mini_od<0LL) Start[k].push_back( make_trio( suma, mini_do, -1 ) );
else Start[k].push_back( make_trio( suma, mini_do, v ) );
//cout << "vS " << v << " " << mini_do << endl;
for(int i=0; i<(int)Kra[v].size(); i++){
if( Odw[ Kra[v][i].first ]==1 ) continue;
// cout << "KRAWEDZ " << v << " " << Kra[v][i].first << endl;
mini=min(mini_od+(ll)Paliwo[ Kra[v][i].first ]-(ll)Kra[v][i].second, (ll)Paliwo[ Kra[v][i].first ]-(ll)Kra[v][i].second);
mini2=min(mini_do, mini_do+(ll)Paliwo[v]-(ll)Kra[v][i].second);
// cout << "mini mini2 " << mini << " " << mini2 << endl;
LiczWynikWrzucOdleglosci(Kra[v][i].first, gdzie_wyn, suma-(ll)Kra[v][i].second+(ll)Paliwo[ Kra[v][i].first ], mini, mini2, k);
}
}
bool Porownaj(trio a, trio b){
if(a.mindo<b.mindo) return 1;
return 0;
}
int PierwszyWiekszy(ll szukana){
int p, k, s;
p=0; k=(int)Odleglosci.size()-1;
while(p<k){
s=(p+k)/2;
if(Odleglosci[s]>=szukana) k=s;
else p=s+1;
}
if(Odleglosci[p]<szukana) return 0;
return (int)Odleglosci.size()-p;
}
int Odejmowanie(ll szukana, int gdzie){
int p, k, s;
p=0; k=(int)Start[gdzie].size()-1;
while(p<k){
s=(p+k)/2;
if(Start[gdzie][s].mindo>=szukana) k=s;
else p=s+1;
}
if(Start[gdzie][p].mindo<szukana) return 0;
return (int)Start[gdzie].size()-p;
}
void LiczWyniki(int aktu){
//cout << "LICZE " << Kra[2][aktu].first << endl;
for(int i=0; i<(int)Start[aktu].size(); i++){
if( Start[aktu][i].v==-1 ) continue;
// cout << "licze " << Start[aktu][i].v << " " << Start[aktu][i].suma << endl;
// cout << "ile wiekszych " << PierwszyWiekszy(-Start[aktu][i].suma) << endl;
// cout << "ile odejmuje " << Odejmowanie(-Start[aktu][i].mindo, aktu) << endl;
Wynik[ Start[aktu][i].v ]+=(PierwszyWiekszy(-Start[aktu][i].suma)-Odejmowanie(-Start[aktu][i].suma, aktu)+1);
}
}
void LiczAktu(int v, vector<int> &Dod){
Odw[v]=1; Dod.push_back(v);
for(int i=0; i<(int)Kra[v].size(); i++){
if(Odw[ Kra[v][i].first ]==0) LiczAktu(Kra[v][i].first, Dod);
}
}
void LiczCentroid(int v){
vector<int>Aktu;
LiczAktu(v, Aktu);
if( (int)Aktu.size()==1 ) return;
for(int i=0; i<(int)Aktu.size(); i++) Odw[Aktu[i]]=Zaz[Aktu[i]];
LiczRozmiar(Aktu[0]);
int c=LiczCentroid(Aktu);
Zaz[c]=1;
for(int i=0; i<(int)Aktu.size(); i++){
Ojciec[Aktu[i]]=Rozmiar[ Aktu[i] ]=0;
Odw[Aktu[i]]=Zaz[Aktu[i]];
}
//cout << endl;
//cout << "CENTROID " << c << endl;
for(int i=0; i<(int)Kra[c].size(); i++){
if( Zaz[ Kra[c][i].first ]==1 ) continue;
LiczWynikWrzucOdleglosci(Kra[c][i].first, c, -(ll)Kra[c][i].second+(ll)Paliwo[Kra[c][i].first], (ll)Paliwo[ Kra[c][i].first ]-(ll)Kra[c][i].second, (ll)Paliwo[c]-(ll)Kra[c][i].second, i);
sort( Start[i].begin(), Start[i].end(), Porownaj );
}
for(int i=0; i<(int)Aktu.size(); i++) Odw[Aktu[i]]=Zaz[Aktu[i]];
//cout << "ODLEGLOSCI " << endl;
sort(Odleglosci.begin(), Odleglosci.end());
//for(int i=0; i<(int)Odleglosci.size(); i++) cout << Odleglosci[i] << " ";
//cout << endl;
for(int i=0; i<(int)Kra[c].size(); i++){
if( Zaz[ Kra[c][i].first ]==1 ) continue;
// cout << "START KORZEEN " << Kra[c][i].first << endl;
// for(int j=0; j<(int)Start[i].size(); j++) cout << Start[i][j].suma << " " << Start[i][j].mindo << " " << Start[i][j].v << endl;
}
//cout << "licze " << c << endl;
for(int i=0; i<(int)Kra[c].size(); i++){
if( Zaz[ Kra[c][i].first ]==0 ) LiczWyniki(i);
Start[i].clear();
}
Odleglosci.clear();
for(int i=0; i<(int)Kra[c].size(); i++){
if( Zaz[ Kra[c][i].first ]==0 ) LiczCentroid( Kra[c][i].first );
}
}
int main (){
int n; ll suma=0LL;
WczytajDane(n);
LiczCentroid(1);
//for(int i=1; i<=n; i++) cout << i << ": " << Wynik[i] << endl;
for(int i=1; i<=n; i++) suma+=(ll)Wynik[i];
cout<<suma<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
5504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
5632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
11560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
274 ms |
13992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
354 ms |
17424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
8296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
11548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
12220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
534 ms |
14624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
664 ms |
17308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
