Submission #968110

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

ll readLL(){
	ll i;
	scanf("%lld",&i);
	return i;
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int Nmax=114514;
struct Edge{
	int to,dist,idx;
};
vector<Edge> tree[Nmax];
bool vRem[Nmax];

int TreeSize(int v,int p){
	int ret=1;
	for(auto e:tree[v])if(e.to!=p&&!vRem[e.to])
		ret+=TreeSize(e.to,v);
	return ret;
}

int FindCentroid(int v,int p,int s){
	int ret=1,mx=0;
	for(auto e:tree[v])if(e.to!=p&&!vRem[e.to]){
		int f=FindCentroid(e.to,v,s);
		if(f<=0)
			return f;
		else{
			ret+=f;
			mx=max(mx,f);
		}
	}
	mx=max(mx,s-ret);
	if(mx*2<=s)
		return -v;
	else
		return ret;
}

void Waf(int v,int p,ll d,vector<ll>& dst){
	dst.PB(d);
	for(auto e:tree[v])if(e.to!=p&&!vRem[e.to])
		Waf(e.to,v,d+e.dist,dst);
}

pair<ll,ll> Solve(int root,ll x){
	int ts=TreeSize(root,-1);
	if(ts==1)
		return MP(0LL,0LL);
	root=-FindCentroid(root,-1,ts);
	vector<vector<ll>> ds,dsSum;
	vector<ll> k,kSum;
	for(auto e:tree[root])if(!vRem[e.to]){
		vector<ll> dst;
		Waf(e.to,root,e.dist,dst);
		ds.PB(dst);
		for(auto v:dst)
			k.PB(v);
	}
	ll f=0,s=0;
	for(auto& d:ds){
		sort(d.begin(),d.end());
		dsSum.PB(d);
		ll last=0;
		for(auto& v:dsSum.back())
			last=v=v+last;
	}
	sort(k.begin(),k.end());
	{
		kSum=k;
		ll last=0;
		for(auto& v:kSum)
			last=v=v+last;
	}
	int j=0;
	for(auto& d:ds){
		for(auto v:d){
			{
				int i=lower_bound(k.begin(),k.end(),x-v)-k.begin();
				if(i>0){
					f+=kSum[i-1]+v*i;
					s+=i;
				}
			}
			{
				int i=lower_bound(d.begin(),d.end(),x-v)-d.begin();
				if(i>0){
					f-=dsSum[j][i-1]+v*i;
					s-=i;
				}
			}
		}
		j++;
	}
	f/=2;
	s/=2;
	{
		int i=lower_bound(k.begin(),k.end(),x)-k.begin();
		if(i>0){
			f+=kSum[i-1];
			s+=i;
		}
	}
	vRem[root]=true;
	for(auto e:tree[root])if(!vRem[e.to]){
		auto g=Solve(e.to,x);
		f+=g.first;
		s+=g.second;
	}
	return MP(f,s);
}

int edgeMin[Nmax];

int main(){
	int n=read(),x=read();
	REP(_,n-1){
		int a=read()-1,b=read()-1,c=read();
		tree[a].PB(Edge{b,c,_});
		tree[b].PB(Edge{a,c,_});
		edgeMin[_]=c;
	}
	ll ans=ll(x)*n*(n-1)/2;
	auto s=Solve(0,x);
	ans-=s.second*x;
	ans+=s.first;
	REP(v,n){
		ll i=LLONG_MAX/3;
		for(auto e:tree[v])
			chmin(i,e.dist);
		for(auto e:tree[v]){
			if(e.dist>x){
				if(int(tree[v].size()+tree[e.to].size())-2<n-2)
					chmin(edgeMin[e.idx],x*2);
				chmin(edgeMin[e.idx],i+x);
			}
		}
	}
	ll bias=0;
	REP(v,n){
		for(auto e:tree[v]){
			if(edgeMin[e.idx]>x){
				bias+=edgeMin[e.idx]-x;
			}
		}
	}
	bias/=2;
	cout<<ans+bias<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:36:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&i);
                ^
./Main.cpp: In function ‘ll readLL()’:
./Main.cpp:42:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&i);
                  ^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:48:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",buf);
                 ^
./Main.cpp: In function ‘char* readCharArray()’:
./Main.cpp:56:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",ret);
                 ^

Judge Result