Solutions of Beautiful tree

Select solution language

The_Blacksiler Created at 0 likes

Ta nhìn thấy được rằng với biểu thức : abs|a[u] - a[v]| sẽ đạt giá trị cực đại khi các giá trị rơi vào đầu mút của [l..r]. Tiếp theo ta phân tích các nhánh con : Nếu đỉnh U chọn l[u] thì đỉnh v (con trực tiếp của đỉnh u) có thể mang giá trị l[v] hoặc r[v] và hiển nhiên v' là con trực tiếp của đỉnh v cũng sẽ sử dụng giá trị ràng buộc là giá trị được sử dụng của đỉnh v. Ta gọi dp[u][j] giá trị lớn nhất tại cây con gốc u và giá trị được chọn tại gốc u là j Với j = 0 thì dp[u][0] sẽ là tại đỉnh u ta chọn l[u] và đỉnh con v có thể chọn r[i] hoặc l[i]: Công thức sẽ là : dp[u][0] += max(dp[v][1] + |l[u] - r[v]|, dp[v][0] + |l[u] - l[v]|) Với j = 1 thì dp[u][1] sẽ là tại đỉnh u ta chọn r[u] và đỉnh con v có thể chọn r[i] hoặc l[i]: Công thức sẽ là : dp[u][1] += max(dp[v][1] + |r[u] - r[v]|, dp[v][0] + |r[u] - l[v]|) Vậy kết quả sẽ là max(dp[u][1], dp[u][0]). Code mẫu : https://ideone.com/I4C1Vy