题解
先随便找一条直径,然后标记这些边,然后看看直径上的点有没有不需要经过标记边的路径,使得其长度等于该点到直径端点的路径长度
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct edge
{
ll to,val;
};
vector<edge> G[200005];
ll maxh=0;
ll node=1;
void dfs(ll now,ll fa,ll height)
{
if(height>maxh)
{
maxh=height;
node=now;
}
for(auto next:G[now])
{
if(next.to==fa) continue;
dfs(next.to,now,height+next.val);
}
}
vector<ll> chain;
ll pre[200005]={0};
bool vis[200005]={0};
bool query(ll now,ll fa,ll des)
{
if(now==des)
{
chain.push_back(now);
vis[now]=1;
return 1;
}
for(auto next:G[now])
{
ll to=next.to;
if(to==fa) continue;
if(query(to,now,des))
{
chain.push_back(now);
ll tem=chain.size()-1;
pre[tem]=pre[tem-1]+next.val;
vis[now]=1;
return 1;
}
}
return 0;
}
ll check(ll now)
{
ll res=0;
for(auto next:G[now])
{
ll to=next.to,val=next.val;
if(vis[to]) continue;
vis[to]=1;
res=max(res,check(to)+val);
vis[to]=0;
}
return res;
}
void solve()
{
ll n;
cin>>n;
for(ll i=1;i<n;i++)
{
ll x,y,w;
cin>>x>>y>>w;
G[x].push_back({y,w});
G[y].push_back({x,w});
}
dfs(1,1,0);
ll node1=node;
maxh=0;
node=node1;
dfs(node1,node1,0);
ll node2=node;
query(node1,node1,node2);
ll len=chain.size();
ll l=0,r=len-1;
for(ll i=1;i<len-1;i++)
{
ll res=check(chain[i]);
ll sum=pre[i];
if(res==sum) l=i;
if(res==pre[len-1]-sum)
{
r=i;
break;
}
}
cout<<pre[len-1]<<'\n';
cout<<r-l<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll t=1;
while(t--) solve();
return 0;
}
标签:val,ll,P3304,next,vis,SDOI2013,node1,直径,now
From: https://www.cnblogs.com/pure4knowledge/p/18303621