題目鏈接

Solution

我們直接找到一條直徑 \(s\),起點(diǎn)為 \(begin\),終點(diǎn)為 \(end\).
從前往后遍歷點(diǎn) \(u\) ,若子樹中最大的距離與 \(dis(u,begin)\) 相等.
很顯然這個(gè)點(diǎn)不在公共線段上,很顯然可以用子樹的中的一段接上,形成一條新的直徑.
然后從后往前遍歷,同樣的道理...
然后找到兩個(gè)節(jié)點(diǎn) \(l,r\) 然后答案即為 \(r-l\).
記得要開 \(longlong\).

Code

#include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn=300008; struct sj{ ll to,next,w; }a[maxn*2]; ll head[maxn],size; ll n,s,x,y,w; ll read() {ll f=1,w=0; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}return f*w; } void add(ll x,ll y,ll w) {a[++size].to=y;a[size].next=head[x];head[x]=size;a[size].w=w; }ll last,num,now,cnt,v[maxn],bcnt; ll ans[maxn],maxx,road[maxn]; ll dist[maxn],b[maxn],ansb[maxn]; ll sum[maxn]; void dfs(ll x) {v[x]=1;road[++cnt]=x;for(ll i=head[x];i;i=a[i].next){ll tt=a[i].to;if(!v[tt]){now+=a[i].w;b[++bcnt]=a[i].w;dfs(tt); cnt--;bcnt--;now-=a[i].w;}}if(now>maxx){num=cnt; last=x; maxx=now;for(ll i=1;i<=cnt;i++)ans[i]=road[i],ansb[i]=b[i];} }void getdist(ll x) {v[x]=1;maxx=max(maxx,now);for(ll i=head[x];i;i=a[i].next){ll tt=a[i].to;if(!v[tt]){now+=a[i].w;getdist(tt);now-=a[i].w;}} }int main() {n=read();for(ll i=1;i<n;i++){x=read(); y=read(); w=read();add(x,y,w); add(y,x,w);}dfs(1);memset(v,0,sizeof(v));maxx=0; cnt=0; now=0;dfs(last);memset(v,0,sizeof(v));for(ll i=1;i<=num;i++)v[ans[i]]=1;for(ll i=2;i<=num;i++)sum[i]=sum[i-1]+ansb[i-1];for(ll i=1;i<=num;i++){maxx=0,getdist(ans[i]),dist[i]=maxx;}ll l=1,r=num;for(int i=1;i<=num;i++)if(sum[i]==dist[i]) l=i;for(int i=num;i>=1;i--)if(sum[num]-sum[i]==dist[i]) r=i;cout<<sum[num]<<endl;cout<<r-l<<endl;}

轉(zhuǎn)載于:https://www.cnblogs.com/Kv-Stalin/p/9508261.html

總結(jié)

以上是生活随笔為你收集整理的[SDOI2013]直径 (树的直径,贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。