Submission #1134986

---

Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N;
    List<int>[] T;
    bool[] b;
    long[,] DP;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        N = int.Parse(Console.ReadLine());
        T = new List<int>[N];
        for(int i=0;i<N;i++){
            T[i] = new List<int>();
        }
        for(int i=0;i<N-1;i++){
            string[] str = Console.ReadLine().Split(' ');
            int a = int.Parse(str[0])-1;
            int b = int.Parse(str[1])-1;
            T[a].Add(b);
            T[b].Add(a);
        }
        int center1;
        int center2;
        int diamater;
        {
            Tree G = new Tree(T);
            G.Center();
            center1 = G.center1;
            center2 = G.center2;
            diamater = G.diamater;
        }
        if(center2 == -1){
            long count = 0;
            b = new bool[N];
            DP = new long[N,2*N+2];
            dfs(center1,diamater/2,N+1);
            for(int i=0;i<2*N+2;i++){
                count = (count + DP[center1,i])%Define.mod;
            }
            sb.Append(count+"\n");
        }
        else{
            long count = 0;
            b = new bool[N];
            DP = new long[N,2*N+2];
            b[center2] = true;
            dfs(center1,diamater/2+1,N);
            dfs(center2,diamater/2,N);
            for(int i=1;i<2*N+1;i++){
                count = (count + DP[center1,i]*(DP[center2,i-1]+DP[center2,i+1]))%Define.mod;
            }
            b = new bool[N];
            DP = new long[N,2*N+2];
            b[center2] = true;
            dfs(center1,diamater/2,N+1);
            dfs(center2,diamater/2+1,N+1);
            for(int i=1;i<2*N+1;i++){
                count = (count + DP[center1,i]*(DP[center2,i-1]+DP[center2,i+1]))%Define.mod;
            }
            b = new bool[N];
            DP = new long[N,2*N+2];
            b[center2] = true;
            dfs(center1,diamater/2,N);
            dfs(center2,diamater/2,N+1);
            for(int i=1;i<2*N+1;i++){
                count = (count + 2*(Define.mod-DP[center1,i])*(DP[center2,i-1]+DP[center2,i+1]))%Define.mod;
            }
            sb.Append(count+"\n");
        }

    }
    void dfs(int v,int l,int Z){
        b[v] = true;
        for(int i=Z-l;i<=Z+l;i++){
            DP[v,i] = 1;
        }
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                dfs(t,l-1,Z);
                for(int j=Z-l;j<=Z+l;j++){
                    DP[v,j] = DP[v,j]*(DP[t,j+1]+DP[t,j-1])%Define.mod;
                }
            }
        }   
    }
}
public class Tree{
    List<int>[] T;
    bool[] b;
    int N;
    int temp1;
    int temp2;
    public int center1;
    public int center2;
    public int diamater;
    public Tree(List<int>[] G){
        T = G;
        N = G.Length;
    } 
    void calcLongestPath(int v){
        b = new bool[N];
        temp1 = 0;
        temp2 = 0;
        dfs1(v,0);
    }
    public int LongestPathDistance(int v){
        calcLongestPath(v);
        return temp1;
    }
    public int LongestPath(int v){
        calcLongestPath(v);
        return temp2;
    }
    public void Diamater(){
        int x1 = LongestPath(0);
        int x2 = LongestPath(x1);
        diamater = temp1;
    }
    public void Center(){
        int x1 = LongestPath(0);
        int x2 = LongestPath(x1);
        diamater = temp1;
        if(diamater % 2 == 0){
            center1 = Search(x1,x2,diamater/2);
            center2 = -1;
        }
        else{
            center1 = Search(x1,x2,diamater/2);
            center2 = Search(x1,x2,diamater/2+1);
        }
    }
    public int Search(int s,int t,int l){
        b = new bool[N];
        dfs2(s,t,0,l);
        return temp1;
    }
    void dfs1(int v,int l){
        b[v] = true;
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                dfs1(t,l+1);
            }
        }
        if(l >= temp1){
            temp1 = l;
            temp2 = v;
        }
    }
    bool dfs2(int v,int o,int l,int d){
        b[v] = true;
        bool x = v == o;
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                x |= dfs2(t,o,l+1,d);
            }
        }
        if(x && l == d){
            temp1 = v;
        }
        return x;
    }
}
public static class Define{
    public const long mod = 1000000007;
}

Submission Info

Judge Result