F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 3124 >> 没过样例却A了
1527148777 @ 2017-12-14 16:07:43
[ Quote ] [ Edit ] [ Delete ] 1#
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
#define N 200001

int tot;
int front[N],nxt[N<<1],to[N<<1],val[N<<1];

LL mx,max_len;
int wh;

LL dis[N];

int path[N],num;

bool use[N];

int cf[N];

void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;
}

void dfs1(int x,int y,LL d)
{
if(d>mx) mx=d,wh=x;
for(int i=front[x];i;i=nxt[i])
{
if(to[i]==y) continue;
dfs1(to[i],x,d+val[i]);
}
}

void dfs2(int x,int y,LL d)
{
dis[x]=d;
if(d>max_len) max_len=d,wh=x;
for(int i=front[x];i;i=nxt[i])
{
if(to[i]==y) continue;
dfs2(to[i],x,d+val[i]);
}
}

void dfs3(int x,LL d)
{
path[++num]=x;
use[x]=true;
for(int i=front[x];i;i=nxt[i])
{
if(dis[to[i]]==d-val[i]) dfs3(to[i],d-val[i]);
}
}

void dfs4(int x,int y,LL d)
{
mx=max(mx,d);
for(int i=front[x];i;i=nxt[i])
{
if(to[i]==y || use[to[i]]) continue;
dfs4(to[i],x,d+val[i]);
}
}

int main()
{
int n;
read(n);
int u,v,w;
for(int i=1;i<n;++i)
{
read(u); read(v); read(w);
add(u,v,w);
}
dfs1(1,0,0);
dfs2(wh,0,0);
cout<<max_len<<'\n';
dfs3(wh,max_len);
int apart=0;
for(int i=2;i<num;++i)
{
mx=0;
dfs4(path[i],0,0);
if(mx==max_len-dis[path[i]]) cf[i]++,apart++;
if(mx==dis[path[i]]) cf[1]++,cf[i]--,apart++;
}
for(int i=2;i<=num;++i) cf[i]+=cf[i-1];
int ans=0;
for(int i=1;i<=num;++i)
{
if(cf[i]==apart) ans++;
}
cout<<ans;
}
[Top] [Previous Page] [Next Page]

HOME Back