Skip to content

Instantly share code, notes, and snippets.

@erjiaqing
Created March 27, 2014 00:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save erjiaqing/9796993 to your computer and use it in GitHub Desktop.
Accepted/1444K/297MS
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cstring>
#include <cstdio>
#include <cmath>
#define x first
#define y second
using namespace std;
const int maxn=10005;
typedef pair<int,int> pii;
vector <pii> e[maxn];
vector <int> dep;
typedef vector <pii>::iterator piii;
typedef vector <int>::iterator ii;
int n,size,s[maxn],f[maxn],root,d[maxn],k,ans;
bool vis[maxn];
void getroot(int now,int fa)
{
int u;
s[now]=1;f[now]=0;
for (piii v=e[now].begin();v!=e[now].end();v++)
{
if ((u=v->x)!=fa && !vis[u])
{
getroot(u,now);
s[now]+=s[u];
f[now]=max(f[now],s[u]);
}
}
f[now]=max(f[now],size-s[now]);
if (f[now]<f[root])
root=now;
}
void getdep(int now,int fa)
{
int u;
dep.push_back(d[now]);
s[now]=1;
for (piii v=e[now].begin();v!=e[now].end();v++)
{
if ((u=v->x)!=fa && !vis[u])
{
d[u]=d[now]+v->y;
getdep(u,now);
s[now]+=s[u];
}
}
}
int calc(int now,int init)
{
dep.clear();d[now]=init;
getdep(now,0);
sort(dep.begin(),dep.end());
int ret=0;
for (ii l=dep.begin(),r=dep.end()-1;l<r;)
{
if (*l+*r<=k)
ret+=r-l++;
else
r--;
}
return ret;
}
void work(int now)
{
int u;
ans+=calc(now,0);
vis[now]=1;
for (piii v=e[now].begin();v!=e[now].end();v++)
{
if (!vis[u=v->x])
{
ans-=calc(u,v->y);
f[0]=size=s[u];
getroot(u,root=0);
work(root);
}
}
}
int main()
{
while ((~scanf("%d%d",&n,&k)) && n)
{
for (int i=0;i<=n;i++)
e[i].clear();
memset(vis,0,sizeof(vis));
int u,v,l;
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&l);
e[u].push_back(pii(v,l));
e[v].push_back(pii(u,l));
}
f[0]=size=n;
getroot(1,root=0);
ans=0;
work(root);
printf("%d\n",ans);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment