题解：AT_mujin_pc_2017_d Oriented Tree

· · 题解

idea from ryz

题目大意很简单，就是说给一棵树的边定向，然后令树上路径 (s,t) 的权值为从 s 开始到 t,所经过的所有边中方向与路径方向相反的边数，答案就是使得树上路径的权值的最大值最小的方案数。

考虑路径，既然是路径，我们肯定想到不妨直接来个最长的路径，那么这个最长的路径的长度权值最大的可能性是最大的，所以不妨设这棵树的直径为 l，把这棵树上最大权值设为 d_{max}，显然有 d_{max}\geq \lceil\frac{l}{2}\rceil 的。考虑能不能取到，那么显然我们就希望让这条路径上的边的方向是正反交错的，那么不妨以树的直径的中点为根，那么树的深度显然是 \lceil\frac{l}{2}\rceil 的，只需要把每一层的边都染成一个颜色即可。

所以现在我们知道了答案，就考虑计数。计数不如还选择直径的中点作为根，记作 root，那么考虑最深的某个点 x,不妨设 d(x,root)-d(root,x)=k,那么继续考虑深度最深的另一个点 y，必然有 d(y,root)-d(root,y)=k。这样，不妨设 g_x=d(x,root)-d(root,x)，那么对于满足 dep_x=dep_y=d_{max} 显然有 g_x=g_y。那么不妨直接对 g 数组平移，让 d_{max} 变成 0，那么考虑其他的点的 g，不妨从下往上考虑，显然，若 dep_x=d_{max}，考虑 g_{fa_x}，显然 fa_x \to x 的这条边是随便定向的，那么直接往上走，可以得出，对于任意一个点 x,都有 dep_x-d_{max}\leq g_x\leq d_{max}-dep_x，考虑下面没有 d_{max} 深度的节点的子树，实际上我们可以假装它下面是有的，然后这么算，这样显然不会影响答案。

那么就可以树形dp了，令 f_{i,j} 表示 i 的子树满足 g_i=j 的方案数，那么就可以从 f_{i,j-1},f_{i,j+1} 转移到 f_{fa_i,j}。那么如果只有一个深度为 d_{max} 的节点怎么办，那就把直径的两个中点拆开来看，每个中点带一棵树，然后分类讨论再容斥一下就可以了。

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
#define int long long
inline int read()
{
    int f=1,re=0;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
    while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^'0'),ch=getchar();
    return re*f;
}
const int mod=1000000007;
vector<int>gra[1005];
int n,a,b,nxt[1005],dd,r1,r2,d,low[1005];
long long dp[1005][1005];
int dfs(int u,int fa)
{
    int re=0;
    for(auto v:gra[u])
    {
        if(v!=fa)
        {
            int tmp=dfs(v,u)+1;
            if(tmp>re) re=tmp,nxt[u]=v;
        }
    }
    return re;
}
void stag(int u,int fa,int tag)
{
    if(tag==0)
    {
        low[u]=0;
    }
    else low[u]=2;
    for(auto v:gra[u])
    {
        if(v!=fa)
        {
            stag(v,u,tag);
        }
    }
}
void solve(int u,int fa,int dep)
{
    memset(dp[u],0,sizeof dp[u]);
    for(int i=dep+low[u];i<=d-dep;i++)
    {
        dp[u][i]=1;
    }
    for(auto v:gra[u])
    {
        if(v!=fa)
        {
            solve(v,u,dep+1);
            for(int i=dep+low[u];i<=d-dep;i++)
            {
                dp[u][i]*=(dp[v][i-1]+dp[v][i+1]);
                dp[u][i]%=mod;
            }
        }
    }
}
int DP(int r1,int r2,int tag)
{
    stag(r1,r2,tag);
    stag(r2,r1,0);
    solve(r1,0,0);
    int ans=0;
    for(int i=0;i<=d;i++)
    {
        ans+=dp[r1][i];
        ans%=mod;
    }
    return ans;
}
signed main()
{
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        gra[u].push_back(v);
        gra[v].push_back(u);
    }
    dfs(1,0);
    int nw=1,ans=0;
    r1=r2=0;
    while(nxt[nw]!=0) nw=nxt[nw];
    memset(nxt,0,sizeof nxt);
    dd=dfs(nw,0);
    for(int i=1;i<=dd;i++)
    {
        nw=nxt[nw];
        if(i*2==dd) r1=nw;
        if(i*2+1==dd) r1=nw;
        if(i*2-1==dd) r2=nw;
    }
    d=dd+(dd&1);
    if((dd&1)==0)
    {
        ans=DP(r1,0,0);
    }
    else
    {
        ans=((DP(r1,r2,0)+DP(r2,r1,0)-DP(r1,r2,1)-DP(r2,r1,1))%mod+mod)%mod;
    }
    if(n==2) cout<<2<<endl;
    else cout<<ans<<endl;
}