树上的选择性DP……
不是很懂其他人的做法,偶然间看到有人用ruby A了,我也就用ruby敲了一蛤
速度有点玄……

题意:
给你一棵树,每个节点都有权值,要你求每个节点到根节点所形成的树链 gcd。
其中每条树链都可以选择一个节点使得权值变为 0 。

思路:
感觉这就是裸题……
只不过就是把数组改成树上了而已。
用一个栈或者队列去遍历这棵树,对于每个节点是否变0都考虑一下就好了……

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n = gets.to_i
a = gets.split.map(&:to_i)
g = Array.new(n) {[]}

(n-1).times do
    u, v = gets.split.map(&:to_i)
    u, v = u-1, v-1
    g[u] << v
    g[v] << u
end

def GCD(a, b) return b == 0 ? a : GCD(b, a%b) end

dp = Array.new(n) { Array.new(2) { [] } }
dp[0] = [[a[0]], [0]]
par = [-1]*n

st = [0]
until st.empty?
    u = st.pop
    g[u].each do |v|
        next if v == par[u]
        par[v] = u
        st.push(v)
        dp[v][0] += dp[u][0].map{|x| GCD(x,a[v])}
        dp[v][1] += dp[u][0]
        dp[v][1] += dp[u][1].map{|x| GCD(x,a[v]) }
        2.times do |i|
            dp[v][i].uniq!
        end
    end
end

print a[0]
for u in 1...n do
    print " #{dp[u][1].max}"
end
Categories: 树形DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

树形DP

CodeForces 855 C Helga Hufflepuff’s Cup

前几天的上分场的树形DP 我敢说思路和我当时想得已经一模一样了,还有半 Read more…

树形DP

CodeForces 19E Fairy

一道二分图性质的应用 + 树形DP ? 看博客里都说是树形DP,但我觉 Read more…

树形DP

HDU4118 这也算树形DP?

传送门 题意: 给你一个无向图,保证联通并且没有环(实质上就是一棵树… Read more…