# P3304 [SDOI2013]直径 题解

## 评论

• 还没有评论

/*

1. 任意选一个点做为根，找最长的一个点p1
2. 用p1做根，找最长一个点q,  p1->q就是一条直径

2.1 p1做根，找出所有最长的点qi，
2.2 p1 -> qi都是直径，找出p1->qi的公共LCA,  lcaq
2.3 任意选一个q1，找出所有最长的点pi
lcap    lcaq
p1 ---- Y-----X-----> q1
p2  ----|     |____> q2
|-- q3

3. dep[lcaq] - dep[lcap] -> 边的数目
*/    

# 朴素算法

#include <iostream>
#include <vector>

#define N 200005

using namespace std;

typedef long long ll;

struct Edge {
int y, w;
};

vector<Edge> g[N];
int n, fa[N], dep[N];
ll len[N], mx = 0;
int p[N], last;

void getMaxs() {
last = 0;
mx = 0;
for (int i = 1; i <= n; i++)
mx = max(mx, len[i]);

for (int i = 1; i <= n; i++)
if (len[i] == mx)
p[++last] = i;
}

void dfs(int x, int _fa, int _dep, ll _len) {
fa[x] = _fa;
dep[x] = _dep;
len[x] = _len;
for (int i = 0; i < g[x].size(); i++) {
int y = g[x][i].y, w = g[x][i].w;
if (y == _fa) continue;
dfs(y, x, _dep + 1, _len + w);
}
}

int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y])
x = fa[x];
while (x != y) {
x = fa[x];
y = fa[y];
}
return x;
}

int getCommonLca() {
int x = p[1];
for (int i = 2; i <= last; i++)
x = lca(x, p[i]);
return x;
}

int main() {
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
Edge e1 = {y, w};
g[x].push_back(e1);
Edge e2 = {x, w};
g[y].push_back(e2);
}
dfs(1, 0, 1, 0);
getMaxs();
dfs(p[1], 0, 1, 0);
getMaxs();
int lca_u = getCommonLca();
dfs(p[1], 0, 1, 0);
getMaxs();
int lca_v = getCommonLca();
cout << mx << endl;
cout << (dep[lca_v] - dep[lca_u]) << endl;
return 0;
}


# 正解

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
struct Edge {
int y, w;
};
const int N=200005;
int n,dep[N],fa[N], lgn, st[N][18];
ll dis[N], mx;
int p[N], last;
vector<Edge> g[N];

void calcMaxs() {
last = 0, mx=0;
for(int i=1; i<=n; i++)
mx = max(mx, dis[i]);
for(int i=1; i<=n; i++)
if(dis[i]==mx)
p[++last] = i;
}

void dfs(int x, int _fa, int _dep, ll _dis) {
fa[x] = _fa;
dep[x] = _dep;
dis[x] = _dis;
st[x][0] = _fa;
for(int i=0; i<g[x].size(); i++) {
int y = g[x][i].y, w=g[x][i].w;
if(y == _fa) continue;
dfs(y, x, _dep+1, _dis+w);
}
}

void initSt() {
for(int j=1; j<=lgn; j++)
for(int i=1; i<=n; i++)
st[i][j] = st[st[i][j-1]][j-1];
}

int lca(int x, int y) {
if(dep[x]<dep[y]) swap(x, y);
/*while(dep[x]>dep[y])
x = fa[x];
while(x!=y) {
x = fa[x];
y = fa[y];
}*/
int d = dep[x] - dep[y];
for(int i=0; i<=lgn; i++)
if((d>>i)&1)
x = st[x][i];

if(x==y) return x;

for(int i=lgn; i>=0; i--) {
if(st[x][i]==st[y][i]) continue;
x = st[x][i];
y = st[y][i];
}
return st[x][0];
}

int commonLca() {
int cl = p[1];
for(int i=2; i<=last; i++)
cl = lca(cl, p[i]);
return cl;
}

int main() {
cin>>n;
lgn = log2(n);
for(int i=1; i<=n-1; i++) {
int x, y, w;
cin>>x>>y>>w;
g[x].push_back((Edge){y, w});
g[y].push_back((Edge){x, w});
}
//第一个端点u
dfs(1, 0, 1, 0);
calcMaxs();
int u = p[1];

//第二个端点v
dfs(u, 0, 1, 0);
calcMaxs();
int v = p[1];
//u为根的时候，p[i]的公共lca
initSt();
int lca_u = commonLca();

//v为根的时候，p[i]的公共lca
dfs(v, 0, 1, 0);
calcMaxs();
initSt();
int lca_v = commonLca();

//求公共边的数目, dep[lca_v]-dep[lca_u]
cout<<mx<<endl;
cout<<dep[lca_v]-dep[lca_u]<<endl;

return 0;
}


## 评论

• 还没有评论

#include<iostream>
#include<cstdio>
#define N 200010
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
int n,pos[N][2],head[N],route[N],num,tot,ans,s,e;
long long ls[N],re[N],d[N],dis[N] ,len,sum;
bool vis[N],v[N];
struct Edge{
int v,next,val;
}edge[N*2];
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();};while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
inline void add(int x,int y,int z){edge[++tot].v=y;edge[tot].next=head[x];edge[tot].val=z;head[x]=tot;}
int bfs(int s){
queue<int>q;q.push(s);memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)d[i]=0;memset(pos,0,sizeof(pos));long long maxn=0;
int maxi;
while(q.size()){
int u=q.front();q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v,z=edge[i].val;
if(vis[v])continue;
d[v]=d[u]+z;
q.push(v);
pos[v][0]=u,pos[v][1]=z;
if(d[v]>maxn)maxn=d[v],maxi=v;
}
}
len=maxn;
return maxi;   //被机房称为毒瘤bfs写法求直径（他们都dfs6行orz）
}
void dfs(int s,int fa,int x){
if(!head[s])return ;
for(int i=head[s];i;i=edge[i].next){
int to=edge[i].v,z=edge[i].val;
if(to==fa||v[to])continue;
d[to]=d[s]+z;
dis[x]=max(dis[x],d[to]);  //dfs过程中求出dis
dfs(to,s,x);
}
}
int main(){
n=read();
for(int i=1;i<=n-1;i++){int x=read(),y=read(),z=read();add(x,y,z);add(y,x,z);}
s=bfs(1);
e=bfs(s);
int t=e;
route[++num]=e;
v[e]=1;
while(t!=s){//标记路径
re[pos[t][0]]=re[t]+pos[t][1];    //在标记路径时求出直径上点到终点e距离，到起点s距离为直径长len-re[x]
t=pos[t][0];
route[++num]=t;
v[t]=1;
}
for(int i=1;i<=num;i++){
int x=route[i];
d[x]=0;
dfs(x,0,x);    //求出dis最长路
}
int tr=1;
for(tr=1;tr<=num;tr++){
int x=route[tr];
if(dis[x]==len-re[x])break;  //如果到s距离为最长路,断点1set
}
int tl=num;
for(tl=num;tl>=1;tl--){
int x=route[tl];
if(dis[x]==re[x])break;//同理断点2
}
ans=abs(tr-tl);//这就是必经边数
printf("%lld\n",len);
printf("%d",ans);
return 0;
}


## 评论

• 1517460958dyc
请合理使用MarkDown

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
static char buf[100010], *h = buf, *t = buf;
return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
x = 0;
char a; bool b = 0;
while(!isdigit(a = gch()))
b = a == '-';
while(isdigit(a))
x = (x << 1) + (x << 3) + a - '0', a = gch();
if(b == 1)
x *= -1;
}

int n, s, t, he, ta, tot = -1, pos, q[200020], head[200020], pre[200020], lx, ly, lz;

struct in
{
int to, ne; lo co;
}ter[400040];

inline void build(int f, int l, lo c)
{
ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

lo ans, sx[200020], tx[200020], sy[200020], ty[200020], de[200020];//x 联通块直径 y最深深度

inline void bfs(int x)
{
memset(de, 0, sizeof(de)), memset(pre, 0, sizeof(pre));
de[q[he = ta = 0] = x] = 1, pos = 0;
while(he <= ta)
{
int qaq = q[he ++]; pos = (de[pos] < de[qaq]) ? qaq : pos;//更新最深的点
for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
{
int to = ter[i].to;
if(de[to] == 0)
pre[to] = qaq, de[q[++ ta] = to] = de[qaq] + ter[i].co;
}
}
}

void dfs(lo *a, lo *b, int no, int fa)
{
lo lx = 0, ly = 0;
for(ri i = head[no]; i >= 0; i = ter[i].ne)
{
int to = ter[i].to;
if(to == fa)
continue;
dfs(a, b, to, no);
b[no] = (b[no] < b[to] + ter[i].co) ? b[to] + ter[i].co : b[no];
if(lx < b[to] + ter[i].co)
ly = lx, lx = b[to] + ter[i].co;
else if(ly < b[to] + ter[i].co)
ly = b[to] + ter[i].co;
a[no] = (a[no] < a[to]) ? a[to] : a[no];//维护子树内部的直径
}
a[no] = (lx + ly < a[no]) ? a[no] : lx + ly;
}

int main()
{
re(n); memset(head, -1, sizeof(head)); s = t = 0;
memset(sx, 0, sizeof(sx)), memset(sy, 0, sizeof(sy));
memset(tx, 0, sizeof(tx)), memset(ty, 0, sizeof(ty));
for(ri i = 1; i < n; i ++)
re(lx), re(ly), re(lz), build(lx, ly, lz);
bfs(1), s = pos, bfs(s), t = pos;//两边bfs确定任意一条直径
dfs(sx, sy, s, 0), dfs(tx, ty, t, 0);//分别以起点和终点为根再去处理子树的信息
for(ri i = t; i != s; i = pre[i])
if(tx[pre[i]] < sx[s] && sx[i] < sx[s])//如果删除这条边之后，两个子树内的直径都小于原树直径
ans ++;//说明这个边一定被所有直径经过
printf("%lld\n%lld", sx[s], ans);
}

## 评论

• 还没有评论

#include<stdio.h>
#define maxn 233333
int father[maxn],head[maxn],n,tot,l,r,p;
long long maxd,dep[maxn];//最长与深度
bool isofd[maxn],flag;//对第一条直径（标准直径）的点标记
struct hhh{int to,w,next;}edge[2*maxn];//邻接表
void add(int x,int y,int z)//加边
{
edge[++tot].to=y;      edge[tot].w=z;
edge[tot].next=head[x];    head[x]=tot;
}
void dfs1(int u,int fa)//算直径的深搜
{
father[u]=fa;//记爸爸
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;if(v==fa)    continue;//只能遍历儿子
dep[v]=dep[u]+edge[i].w;
if(dep[v]>maxd)    p=v,maxd=dep[v];//最远（深）的点和距离
dfs1(v,u);
}
}
void dfs2(int u,int fa)//搜索标准直径上每一个点的子树深度
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;if(v==fa||isofd[v])    continue;
dep[v]=dep[u]+edge[i].w;//dep没用了，随便改
if(dep[v]>maxd)    maxd=dep[v];//最深
dfs2(v,u);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);        add(b,a,c);
}
dfs1(1,0);    l=p;//以任意一个点为根搜最深作为标准直径左端点
dep[p]=maxd=0;    dfs1(l,0);    r=p;//以左端点为根搜最深即为又端点
printf("%lld\n",maxd);
//喜：直径结束！！QAQ
for(int i=r;i;i=father[i])    isofd[i]=true;//标记标准诗经上的点
int ll=l,rr=r;                    //避免搜索的深度与标准直径重复
for(int i=father[rr];i!=ll;i=father[i])
{
int ld=dep[i],rd=dep[rr]-dep[i];//该点到左右端点的距离
dep[i]=maxd=0;//dep过去就没用了，清空状态，搜索子树深度
dfs2(i,0);
if(maxd==rd)    r=i;
//如果子树深度与到右端点的距离相同，那么意味着从这点还有其他直径分出，缩短树干右端点
if(maxd==ld&&!flag)    flag=true,l=i;//因为从右遍历，左端点剪一次为最佳
}
maxd=1;//改记缩短后的r~l经过边数
for(int i=father[r];i!=l;i=father[i])    maxd++;
printf("%d\n",maxd);
return 0;
}