[SDOI2013]直径 (树的直径,贪心)

题目链接

Solution

我们直接找到一条直径 \(s\),起点为 \(begin\),终点为 \(end\).
从前往后遍历点 \(u\) ,若子树中最大的距离与 \(dis(u,begin)\) 相等.
很显然这个点不在公共线段上,很显然可以用子树的中的一段接上,形成一条新的直径.
然后从后往前遍历,同样的道理...
然后找到两个节点 \(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;}

转载于:https://www.cnblogs.com/Kv-Stalin/p/9508261.html

总结

以上是生活随笔为你收集整理的[SDOI2013]直径 (树的直径,贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。