Submission #9619555


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
AB = list(list(map(int,readline().split())) for _ in range(N-1))
M = int(readline())
UV = list(list(map(int,readline().split())) for _ in range(M))

graph = [[] for _ in range(N+1)]
for i, (a,b) in enumerate(AB):
    graph[a].append((b,i))
    graph[b].append((a,i))

def get_path(U,V):
    INF = 100
    visited = [False] * (N+1)
    pred = [None] * (N+1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v,i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v,i = pred[w]
        w = v
        path += 1<<i
    return path

condition_path = [get_path(u,v) for u,v in UV]

S = np.zeros(1<<M,np.int64)
sgn = np.ones(1<<M,np.int64)
for i in range(M):
    S[1<<i:1<<(i+1)] = S[:1<<i] | condition_path[i]
    sgn[1<<i:1<<(i+1)] = -sgn[:1<<i]

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n_edges = popcnt(S)

x = 1<<(N-1-n_edges)
answer = (x * sgn).sum()
print(answer)

Submission Info

Submission Time
Task F - Tree and Constraints
User maspy
Language Python (3.4.3)
Score 600
Code Size 1651 Byte
Status AC
Exec Time 230 ms
Memory 61600 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All dense_01.txt, dense_02.txt, dense_03.txt, dense_04.txt, dense_05.txt, large_ans.txt, line_01.txt, line_02.txt, line_03.txt, no_overlap.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, star_01.txt, star_02.txt, star_03.txt
Case Name Status Exec Time Memory
dense_01.txt AC 226 ms 61600 KB
dense_02.txt AC 152 ms 14000 KB
dense_03.txt AC 150 ms 13992 KB
dense_04.txt AC 229 ms 61600 KB
dense_05.txt AC 152 ms 13992 KB
large_ans.txt AC 149 ms 12480 KB
line_01.txt AC 228 ms 61600 KB
line_02.txt AC 228 ms 61600 KB
line_03.txt AC 228 ms 61596 KB
no_overlap.txt AC 229 ms 61596 KB
random_01.txt AC 185 ms 37016 KB
random_02.txt AC 228 ms 61584 KB
random_03.txt AC 185 ms 37024 KB
random_04.txt AC 230 ms 61588 KB
random_05.txt AC 185 ms 37028 KB
random_06.txt AC 229 ms 61596 KB
random_07.txt AC 185 ms 36976 KB
random_08.txt AC 185 ms 37024 KB
random_09.txt AC 228 ms 61588 KB
random_10.txt AC 229 ms 61552 KB
sample_01.txt AC 148 ms 12480 KB
sample_02.txt AC 148 ms 12492 KB
sample_03.txt AC 150 ms 12444 KB
sample_04.txt AC 150 ms 12492 KB
star_01.txt AC 229 ms 61600 KB
star_02.txt AC 227 ms 61600 KB
star_03.txt AC 228 ms 61588 KB