This is suncongbo's blog.↵
This entry is just for testing.↵
↵
##Markdown Test↵
#####Markdown Test↵
MD Test: $\sum^{n}_{i=1} a_i$↵
↵
MD Test: $$\sum^{n}_{i=1} a_i$$↵
↵
↵
Created, edited and deleted successfully.↵
↵
Inline Code:↵
`↵
int main()↵
{↵
printf("Hello World!\n"); //Hello world↵
}↵
`↵
↵
Reference:↵
↵
[user:suncongbo,2017-10-13] refers to me at **20171013**↵
↵
[user:suncongbo,2018-05-30] refers to me at **20180530**↵
↵
[contest:869]↵
↵
[problem:438A] refers to a contest by [user:vfleaking,2018-06-23]↵
↵
Block Code:↵
**Empty lines are now allowed in the code.**↵
*An empty line is requested above the code.*↵
↵
~~~~~↵
#include<cstdio>↵
#include<algorithm>↵
using namespace std;↵
const int N = 2e5;↵
const int C = 1e6;↵
const int INF = 1e8;↵
struct Edge {int nxt,v,w;} e[(N<<1)+2];↵
int tmp[N+2];↵
int t[C+2];↵
int dis[N+2];↵
int dep[N+2];↵
int fe[N+2];↵
int sz[N+2];↵
int cur[N+2];↵
bool vis[N+2];↵
int n,m,mn,c,rt,siz,ans,tp;↵
void addedge(int u,int v,int w)↵
{↵
m++; e[m].v = v; e[m].w = w;↵
e[m].nxt = fe[u]; fe[u] = m;↵
}↵
void getroot(int u,int prv)↵
{↵
sz[u] = 1; cur[u] = 0;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(e[i].v==prv || vis[e[i].v]==true) continue;↵
getroot(e[i].v,u);↵
sz[u] += sz[e[i].v]; cur[u] = max(cur[u],sz[e[i].v]);↵
}↵
cur[u] = max(cur[u],siz-sz[u]);↵
if(cur[u]<mn) {mn = cur[u]; rt = u;}↵
}↵
void dfs(int u,int prv)↵
{↵
tp++; tmp[tp] = u;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true || e[i].v==prv) continue;↵
dep[e[i].v] = dep[u]+1; dis[e[i].v] = dis[u]+e[i].w;↵
if(dis[e[i].v]>c) dis[e[i].v] = c+1;↵
dfs(e[i].v,u);↵
}↵
}↵
void pdc(int u)↵
{↵
vis[u] = true;↵
tp = 0;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true) continue;↵
dis[e[i].v] = e[i].w; dep[e[i].v] = 1; ↵
dfs(e[i].v,u);↵
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<c) ans = min(ans,t[c-dis[tmp[j]]]+dep[tmp[j]]);}↵
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<=c) t[dis[tmp[j]]] = min(t[dis[tmp[j]]],dep[tmp[j]]);}↵
ans = min(ans,t[c]);↵
}↵
for(int i=1; i<=tp; i++) {if(dis[tmp[i]]<=c) t[dis[tmp[i]]] = INF;}↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true) continue;↵
rt = 0; mn = INF; siz = sz[e[i].v];↵
getroot(e[i].v,0); pdc(rt);↵
}↵
}↵
int main()↵
{↵
scanf("%d%d",&n,&c); m = 0;↵
if(c==0) {puts("0"); return 0;}↵
for(int i=1; i<n; i++)↵
{↵
int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++;↵
if(z>c) z = c+1;↵
addedge(x,y,z); addedge(y,x,z);↵
}↵
for(int i=1; i<=c; i++) t[i] = INF;↵
siz = sz[1] = n; rt = 0; ans = INF; mn = INF;↵
getroot(1,0); pdc(rt);↵
printf("%d\n",ans==INF ? -1 : ans);↵
return 0;↵
}↵
~~~~~↵
↵
This entry is just for testing.↵
↵
##Markdown Test↵
#####Markdown Test↵
MD Test: $\sum^{n}_{i=1} a_i$↵
↵
MD Test: $$\sum^{n}_{i=1} a_i$$↵
↵
↵
Created, edited and deleted successfully.↵
↵
Inline Code:↵
`↵
int main()↵
{↵
printf("Hello World!\n"); //Hello world↵
}↵
`↵
↵
Reference:↵
↵
[user:suncongbo,2017-10-13] refers to me at **20171013**↵
↵
[user:suncongbo,2018-05-30] refers to me at **20180530**↵
↵
[contest:869]↵
↵
[problem:438A] refers to a contest by [user:vfleaking,2018-06-23]↵
↵
Block Code:↵
**Empty lines are now allowed in the code.**↵
*An empty line is requested above the code.*↵
↵
~~~~~↵
#include<cstdio>↵
#include<algorithm>↵
using namespace std;↵
const int N = 2e5;↵
const int C = 1e6;↵
const int INF = 1e8;↵
struct Edge {int nxt,v,w;} e[(N<<1)+2];↵
int tmp[N+2];↵
int t[C+2];↵
int dis[N+2];↵
int dep[N+2];↵
int fe[N+2];↵
int sz[N+2];↵
int cur[N+2];↵
bool vis[N+2];↵
int n,m,mn,c,rt,siz,ans,tp;↵
void addedge(int u,int v,int w)↵
{↵
m++; e[m].v = v; e[m].w = w;↵
e[m].nxt = fe[u]; fe[u] = m;↵
}↵
void getroot(int u,int prv)↵
{↵
sz[u] = 1; cur[u] = 0;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(e[i].v==prv || vis[e[i].v]==true) continue;↵
getroot(e[i].v,u);↵
sz[u] += sz[e[i].v]; cur[u] = max(cur[u],sz[e[i].v]);↵
}↵
cur[u] = max(cur[u],siz-sz[u]);↵
if(cur[u]<mn) {mn = cur[u]; rt = u;}↵
}↵
void dfs(int u,int prv)↵
{↵
tp++; tmp[tp] = u;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true || e[i].v==prv) continue;↵
dep[e[i].v] = dep[u]+1; dis[e[i].v] = dis[u]+e[i].w;↵
if(dis[e[i].v]>c) dis[e[i].v] = c+1;↵
dfs(e[i].v,u);↵
}↵
}↵
void pdc(int u)↵
{↵
vis[u] = true;↵
tp = 0;↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true) continue;↵
dis[e[i].v] = e[i].w; dep[e[i].v] = 1; ↵
dfs(e[i].v,u);↵
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<c) ans = min(ans,t[c-dis[tmp[j]]]+dep[tmp[j]]);}↵
for(int j=1; j<=tp; j++) {if(dis[tmp[j]]<=c) t[dis[tmp[j]]] = min(t[dis[tmp[j]]],dep[tmp[j]]);}↵
ans = min(ans,t[c]);↵
}↵
for(int i=1; i<=tp; i++) {if(dis[tmp[i]]<=c) t[dis[tmp[i]]] = INF;}↵
for(int i=fe[u]; i; i=e[i].nxt)↵
{↵
if(vis[e[i].v]==true) continue;↵
rt = 0; mn = INF; siz = sz[e[i].v];↵
getroot(e[i].v,0); pdc(rt);↵
}↵
}↵
int main()↵
{↵
scanf("%d%d",&n,&c); m = 0;↵
if(c==0) {puts("0"); return 0;}↵
for(int i=1; i<n; i++)↵
{↵
int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++;↵
if(z>c) z = c+1;↵
addedge(x,y,z); addedge(y,x,z);↵
}↵
for(int i=1; i<=c; i++) t[i] = INF;↵
siz = sz[1] = n; rt = 0; ans = INF; mn = INF;↵
getroot(1,0); pdc(rt);↵
printf("%d\n",ans==INF ? -1 : ans);↵
return 0;↵
}↵
~~~~~↵
↵
