[SDOI2013]直径-解题报告
i207M
2019-04-12 16:36:06
发现自己的做法和其他题解的都不一样，感觉自己的做法更简单，细节更少一点，不用考虑各种情况。
回想最短路的必经边如何求？我们统计S到T的最短路条数，如果一条边$cnt[S][u]\times cnt[v][T]=cnt[S][T]$，那么这条边就是必经边。
这道题同理，我们可以两次dfs时树形DP，求出dp值和最优解的方案数，如果由这条边构成的直径的方案数等于全局方案数，那么这条边就必选。
```cpp
#define N 200005
int n;
int head[N],cnte=1,v[N*2],nx[N*2],w[N*2];
il void adde(int uu,int vv,int ww)
{
v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte,w[cnte]=ww;
}
struct Data
{
LL w,cnt;
Data() {}
Data(const LL &_w,const LL &_cnt) {w=_w,cnt=_cnt;}
il void comb(const Data &v)
{
if(v.w>w) w=v.w,cnt=v.cnt;
else if(v.w==w) cnt+=v.cnt;
}
};
Data f[N],D,g[N];
int fe[N];
void dfs(int x,int _fa)
{
f[x].w=0,f[x].cnt=1;
for(ri i=head[x]; i; i=nx[i])
{
if(v[i]==_fa) continue;
fe[v[i]]=w[i];
dfs(v[i],x);
D.comb(Data(f[x].w+f[v[i]].w+w[i],f[x].cnt*f[v[i]].cnt));
f[x].comb(Data(f[v[i]].w+w[i],f[v[i]].cnt));
}
}
int ans;
Data qz[N],hz[N];
il void check(const Data &v)
{
if(D.w==v.w&&D.cnt==v.cnt) ++ans;
}
void efs(int x,int _fa)
{
if(!_fa) g[x].cnt=1;
else
{
g[x]=Data(g[_fa].w+fe[x],g[_fa].cnt);
g[x].comb(Data(qz[x].w+fe[x],qz[x].cnt)),g[x].comb(Data(hz[x].w+fe[x],hz[x].cnt));
check(Data(g[x].w+f[x].w,g[x].cnt*f[x].cnt));
}
static int st[N]; int tp=0;
Data t; t.w=t.cnt=0;
for(ri i=head[x]; i; i=nx[i])
{
if(v[i]==_fa) continue;
st[++tp]=v[i];
qz[v[i]]=t;
t.comb(Data(f[v[i]].w+w[i],f[v[i]].cnt));
}
t.w=t.cnt=0;
for(ri i=tp; i>=1; --i)
{
hz[st[i]]=t;
t.comb(Data(f[st[i]].w+fe[st[i]],f[st[i]].cnt));
}
for(ri i=head[x]; i; i=nx[i])
{
if(v[i]==_fa) continue;
efs(v[i],x);
}
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
// freopen("ot.out","w",stdout);
#endif
in(n);
for(ri i=1,a,b,c; i<n; ++i)
{
in(a,b,c);
adde(a,b,c),adde(b,a,c);
}
dfs(1,0);
efs(1,0);
out(D.w);
out(ans);
return 0;
}
```