Problem:


Score : 1100 points

Problem Statement

We have a tree G with N vertices numbered 1 to N.
The i-th edge of G connects Vertex a_i and Vertex b_i.

Consider adding zero or more edges in G, and let H be the graph resulted.

Find the number of graphs H that satisfy the following conditions, modulo 998244353.

H does not contain self-loops or multiple edges.

The diameters of G and H are equal.

For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.

Constraints

 3 \le N \le 2 \times 10^5 

 1 \le a_i, b_i \le N 

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

Print the answer.

Sample Input 1

6
1 6
2 1
5 2
3 4
2 3

Sample Output 1

3

For example, adding the edges (1, 5), (3, 5) in G satisfies the conditions.

Sample Input 2

3
1 2
2 3

Sample Output 2

1

The only graph H that satisfies the conditions is G.

Sample Input 3

9
1 2
2 3
4 2
1 7
6 1
2 5
5 9
6 8

Sample Output 3

27

Sample Input 4

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17

Sample Output 4

78732



Sample input:
6
1 6
2 1
5 2
3 4
2 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod=998244353

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

Q=[1]
D=[-1]*(N+1)
D[1]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)
            
f=D.index(max(D))
Q=[f]
D=[-1]*(N+1)
D[f]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)

MAX=max(D)
l=D.index(MAX)
Q=[l]
D2=[-1]*(N+1)
D2[l]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D2[to]==-1:
            D2[to]=D2[x]+1
            Q.append(to)

if MAX%2==0:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2:
            c=i
            break
        
    TOP_SORT=[]
    
    Q=[c]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c]=0
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[[0,0,0] for i in range(3)] for i in range(N+1)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x][1][1]=1

        elif len(E[x])==1:
            DP[x][0][0]=1
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue

                X=[[0,0,0] for i in range(3)]
                for i in range(3):
                    for j in range(3):
                        X[0][0]+=DP[to][i][j]
                        X[i][0]+=DP[to][i][j]
                        X[0][j]+=DP[to][i][j]
                
                if DP[x]==[[0,0,0] for i in range(3)]:
                    DP[x]=X
                    
                else:
                    Y=[[0,0,0] for i in range(3)]

                    for i in range(3):
                        for j in range(3):
                            for k in range(3):
                                for l in range(3):
                                    Y[min(2,i+k)][min(2,j+l)]=(Y[min(2,i+k)][min(2,j+l)]+X[i][j]*DP[x][k][l])%mod

                    DP[x]=Y

    #print(DP)
    print(DP[c][1][1]*pow(2,mod-2,mod)%mod)
    
else:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2+1:
            c1=i
        elif D[i]==MAX//2+1 and D2[i]==MAX//2:
            c2=i
        
    TOP_SORT=[]
    
    Q=[c1,c2]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c1]=0
    D[c2]=0
    
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[[0,0,0] for i in range(3)] for i in range(N+1)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x][1][1]=1

        elif len(E[x])==1:
            DP[x][0][0]=1
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue

                X=[[0,0,0] for i in range(3)]
                for i in range(3):
                    for j in range(3):
                        X[0][0]+=DP[to][i][j]
                        X[i][0]+=DP[to][i][j]
                        X[0][j]+=DP[to][i][j]
                
                if DP[x]==[[0,0,0] for i in range(3)]:
                    DP[x]=X
                    
                else:
                    Y=[[0,0,0] for i in range(3)]

                    for i in range(3):
                        for j in range(3):
                            for k in range(3):
                                for l in range(3):
                                    Y[min(2,i+k)][min(2,j+l)]=(Y[min(2,i+k)][min(2,j+l)]+X[i][j]*DP[x][k][l])%mod

                    DP[x]=Y

    #print(DP)
    print(DP[c2][1][1]*pow(2,mod-2,mod)%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod=998244353

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

Q=[1]
D=[-1]*(N+1)
D[1]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)
            
f=D.index(max(D))
Q=[f]
D=[-1]*(N+1)
D[f]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)

MAX=max(D)
l=D.index(MAX)
Q=[l]
D2=[-1]*(N+1)
D2[l]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D2[to]==-1:
            D2[to]=D2[x]+1
            Q.append(to)

if MAX%2==0:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2:
            c=i
            break
        
    TOP_SORT=[]
    
    Q=[c]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c]=0
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[[0,0,0] for i in range(3)] for i in range(N+1)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x][1][1]=1

        elif len(E[x])==1:
            DP[x][0][0]=1
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue

                X=[[0,0,0] for i in range(3)]
                for i in range(3):
                    for j in range(3):
                        X[0][0]+=DP[to][i][j]
                        X[i][0]+=DP[to][i][j]
                        X[0][j]+=DP[to][i][j]
                
                if DP[x]==[[0,0,0] for i in range(3)]:
                    DP[x]=X
                    
                else:
                    Y=[[0,0,0] for i in range(3)]

                    for i in range(3):
                        for j in range(3):
                            for k in range(3):
                                for l in range(3):
                                    Y[min(2,i+k)][min(2,j+l)]=(Y[min(2,i+k)][min(2,j+l)]+X[i][j]*DP[x][k][l])%mod

                    DP[x]=Y

    #print(DP)
    print(DP[c][1][1]*pow(2,mod-2,mod)%mod)
    
else:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2+1:
            c1=i
        elif D[i]==MAX//2+1 and D2[i]==MAX//2:
            c2=i
        
    TOP_SORT=[]
    
    Q=[c1,c2]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c1]=0
    D[c2]=0
    P[c1]=c2
    P[c2]=c1
    
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[[0,0,0] for i in range(3)] for i in range(N+1)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x][1][1]=1

        elif len(E[x])==1:
            DP[x][0][0]=1
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue

                X=[[0,0,0] for i in range(3)]
                for i in range(3):
                    for j in range(3):
                        X[0][0]+=DP[to][i][j]
                        X[i][0]+=DP[to][i][j]
                        X[0][j]+=DP[to][i][j]
                
                if DP[x]==[[0,0,0] for i in range(3)]:
                    DP[x]=X
                    
                else:
                    Y=[[0,0,0] for i in range(3)]

                    for i in range(3):
                        for j in range(3):
                            for k in range(3):
                                for l in range(3):
                                    Y[min(2,i+k)][min(2,j+l)]=(Y[min(2,i+k)][min(2,j+l)]+X[i][j]*DP[x][k][l])%mod

                    DP[x]=Y

    #print(DP[c1])
    #print(DP[c2])
    print(sum(DP[c1][1])*sum(DP[c2][1])%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
mod=998244353

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

Q=[1]
D=[-1]*(N+1)
D[1]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)
            
f=D.index(max(D))
Q=[f]
D=[-1]*(N+1)
D[f]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)

MAX=max(D)
l=D.index(MAX)
Q=[l]
D2=[-1]*(N+1)
D2[l]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D2[to]==-1:
            D2[to]=D2[x]+1
            Q.append(to)

if MAX%2==0:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2:
            c=i
            break
        
    TOP_SORT=[]
    
    Q=[c]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c]=0
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[[0,0,0] for i in range(3)] for i in range(N+1)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x][1][1]=1

        elif len(E[x])==1:
            DP[x][0][0]=1
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue

                X=[[0,0,0] for i in range(3)]
                for i in range(3):
                    for j in range(3):
                        X[0][0]+=DP[to][i][j]
                        X[i][0]+=DP[to][i][j]
                        X[0][j]+=DP[to][i][j]
                
                if DP[x]==[[0,0,0] for i in range(3)]:
                    DP[x]=X
                    
                else:
                    Y=[[0,0,0] for i in range(3)]

                    for i in range(3):
                        for j in range(3):
                            for k in range(3):
                                for l in range(3):
                                    Y[min(2,i+k)][min(2,j+l)]=(Y[min(2,i+k)][min(2,j+l)]+X[i][j]*DP[x][k][l])%mod

                    DP[x]=Y

    #print(DP)
    print(DP[c][1][1]*pow(2,mod-2,mod)%mod)
    
else:
    A[10000]

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
mod=998244353

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

Q=[1]
D=[-1]*(N+1)
D[1]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)
            
f=D.index(max(D))
Q=[f]
D=[-1]*(N+1)
D[f]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D[to]==-1:
            D[to]=D[x]+1
            Q.append(to)

MAX=max(D)
l=D.index(MAX)
Q=[l]
D2=[-1]*(N+1)
D2[l]=0
while Q:
    x=Q.pop()
    for to in E[x]:
        if D2[to]==-1:
            D2[to]=D2[x]+1
            Q.append(to)

if MAX%2==0:
    for i in range(N+1):
        if D[i]==MAX//2 and D2[i]==MAX//2:
            c=i
            break
        
    TOP_SORT=[]
    
    Q=[c]
    D=[-1]*(N+1)
    P=[-1]*(N+1)
    D[c]=0
    while Q:
        x=Q.pop()
        TOP_SORT.append(x)
        for to in E[x]:
            if D[to]==-1:
                D[to]=D[x]+1
                Q.append(to)
                P[to]=x

    DP=[[0,0,0] for i in range(N+1)]
    # 中心からの距離が条件を満たすものが、0個, 1個, 2個以上

    for x in TOP_SORT[::-1]:
        if D[x]==MAX//2:
            DP[x]=[0,1,0]

        elif len(E[x])==1:
            DP[x]=[1,0,0]

        elif x==c:
            True
            
        else:
            for to in E[x]:
                if to==P[x]:
                    continue
                xt,yt,zt=DP[to]
                x1,y1,z1=xt*3+yt*2+zt*2,yt,zt
                
                if DP[x]==[0,0,0]:
                    DP[x]=[x1,y1,z1]
                else:
                    x0,y0,z0=DP[x]
                    DP[x]=[x0*x1%mod,(x1*y0+x0*y1)%mod,(y0*y1+z0*(x1+y1+z1)+z1*(x0+y0))%mod]

    ANS=[0,0,0] # 0個, 1個, 2個ちょうど
    for to in E[c]:
        xt,yt,zt=DP[to]
        x1,y1,z1=xt*3+yt*2+zt*2,yt,zt
        
        if ANS==[0,0,0]:
            ANS=[x1,y1,z1]

        else:
            x0,y0,z0=ANS
            ANS=[x0*x1%mod,(x1*y0+x0*y1)%mod,(y1*y0+y0*y1)%mod]

    print(ANS[2]*pow(2,mod-2,mod)%mod)
else:
    A[10000]

Submission status: Runtime Error

Solution code:
BASE = 9973
MOD1 = 10 ** 9 + 7
MOD2 = 998244353


class RollingHash:
    # 文字列Sのローリングハッシュを構築
    # 計算量: O(N)
    def __init__(self, S, MOD):
        self.MOD = MOD
        # acc[i]はS[0:i]のハッシュ値となる
        self.acc = [0]
        a = 0
        # 累積和を計算するイメージ
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    # S[i:j]のハッシュ値を返す
    # 計算量: O(1)
    def hash(self, i, j):
        # 累積和を用いて部分区間の和を計算するイメージ
        # 注意: 基数によるオフセットをキャンセルする必要がある
        offset = pow(BASE, i, self.MOD)
        # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
        # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
        offset_inv = pow(offset, self.MOD - 2, self.MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % self.MOD


N = int(input())
S = input()

# Sのローリングハッシュを計算しておく
rolling1 = RollingHash(S, MOD1)
rolling2 = RollingHash(S, MOD2)

# 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
# つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
#   - 0以上c以下の整数mについてP(m)は真
#   - cより大きい整数mについてP(m)は偽
# ※ Pは単調関数ということ
# このcを二分探索で発見すれば高速化できる！

# P(ok)は真
ok = 0
# P(ng)は偽
ng = N
while ng - ok > 1:
    # 区間[ok, ng)の中央値をmとする
    m = (ok + ng) // 2

    # 長さmのダジャレが存在するか判定する
    # 長さmのformerのハッシュ値のキャッシュ
    former_cache1 = set()
    former_cache2 = set()
    p = False
    # latterに着目してループを回す
    for i in range(m, N):
        # ダジャレ長を決め打ちしているのでjを直接計算できる
        j = i + m
        # S[i:j]がSをはみ出したらループ終了
        if j > N:
            break
        # formerのハッシュ値をキャッシュする
        former_cache1.add(rolling1.hash(i - m, i))
        former_cache2.add(rolling2.hash(i - m, i))
        # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
        # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
        if (
            rolling1.hash(i, j) in former_cache1
            and rolling2.hash(i, j) in former_cache2
        ):
            p = True
    # 区間[ok, ng) を更新
    if p:
        ok = m
    else:
        ng = m
# whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
ans = ok

print(ans)