首页 > 试题广场 >

偶数路径2.0

[编程题]偶数路径2.0

热度指数：143 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游获得了一棵包含 $n$ 个节点的树，每个节点上都有一个数字 $a_i$ 。

对于一条路径的权值为 $gcd(a_{b_1},a_{b_2},a_{b_3},\dots,a_{b_k})$ ，其中 $b_1,b_2,b_3,\dots,b_k$ 是路径上的节点编号，当路径上只有一个点路径权值即为该点的点权。

请你统计树中有多少条简单路径的权值为偶数。

我们认为 $u\rightarrow v$ 和 $v\rightarrow u$ 是同一条路径。特别的，我们认为 $u\rightarrow u$ 也是一条路径。

输入描述:

第一行一个整数 ，表示树的结点总数。

第二行  个整数，第  个为 ，表示结点的权值。

接下来  行，每行两个整数 ，表示结点  和结点  之间通过一条无向边连接。

输出描述:

一个整数，表示有多少条简单路径的权值为偶数。

示例1

输入

输出

算法知识视频讲解

查看答案及解析

geniecyy

import sys
from collections import defaultdict
n=int(input())
sys.setrecursionlimit(200005)

val=[0]+list(map(int,input().strip().split()))
edge=defaultdict(list)
for t in range(n-1):
    u,v=list(map(int,input().strip().split()))
    edge[u].append(v)
    edge[v].append(u)

ans=0
def dfs(cur,p):
    global ans
    flag=not val[cur]%2
    o=1 if flag else 0
    son=0
    sum_=0
    square_=0
    for i in edge[cur]:
        if i==p:
            continue
        c=dfs(i,cur)
        if flag:
            son+=c
            sum_+=c
            square_+=c**2
    res=    o+son+(sum_**2-square_)//2
    ans+=res
    return o+son 
        
        



    

    


dfs(1,0)
print(ans)

发表于 2025-09-09 18:30:35 回复(0)