题目描述
题目简述：树版[k取方格数] 众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。 今天他得到了一款新游戏《XX半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的） “为什么你还没玩就知道每个场景的价值呢？” “我已经看到结局了。”输入
第一行两个正整数n,k 第二行n个正整数，表示每个场景的价值 以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲） 保证场景1为根节点输出
输出一个整数表示答案样例输入
5 2 4 3 2 1 1 1 2 1 5 2 3 2 4
样例输出
10
题解：这道题算是一道线段树的好题，所以来写篇博客记录一下。首先我们要明确一点：当一个点被选了以后，有影响的仅仅是它的子树，而且每取一次，肯定是要取到叶子节点的，所以叶子节点的权值（离根节点的距离）会被不断改变，所以这题变成了一道边修改边查询的问题，而且有一个性质是子树的dfs序一定是一段连续的区间，所以一定是区间修改，于是这题就变成了一道区间修改单点查询的题，所以就用线段树来做，线段树来维护区间最大值和区间最大值的位置。
总结：当拿到一道题时无从下手时，首先找性质，即通过性质来确定算法和数据结构。
#include <cstdio> #include <algorithm> #define N 200010 #define lson l , mid , x << 1 #define rson mid + 1 , r , x << 1 | 1 using namespace std; typedef long long ll; int fa[N] , head[N] , to[N] , next[N] , cnt , pos[N] , ref[N] , last[N] , tot , mp[N << 2] , del[N]; ll w[N] , v[N] , mx[N << 2] , tag[N << 2]; void add(int x , int y) { to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x) { int i; v[x] = v[fa[x]] + w[x] , pos[x] = ++tot , ref[tot] = x; for(i = head[x] ; i ; i = next[i]) dfs(to[i]); last[x] = tot; } void pushup(int x) { int l = x << 1 , r = x << 1 | 1; if(mx[l] > mx[r]) mx[x] = mx[l] , mp[x] = mp[l]; else mx[x] = mx[r] , mp[x] = mp[r]; } void pushdown(int x) { if(tag[x]) { int l = x << 1 , r = x << 1 | 1; mx[l] -= tag[x] , mx[r] -= tag[x]; tag[l] += tag[x] , tag[r] += tag[x]; tag[x] = 0; } } void build(int l , int r , int x) { if(l == r) { mx[x] = v[ref[l]] , mp[x] = l; return; } int mid = (l + r) >> 1; build(lson) , build(rson); pushup(x); } void update(int b , int e , ll a , int l , int r , int x) { if(b <= l && r <= e) { mx[x] -= a , tag[x] += a; return; } pushdown(x); int mid = (l + r) >> 1; if(b <= mid) update(b , e , a , lson); if(e > mid) update(b , e , a , rson); pushup(x); } int main() { int n , k , i , x , y; ll ans = 0; scanf("%d%d" , &n , &k); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &w[i]); for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , fa[y] = x , add(x , y); dfs(1); build(1 , n , 1); while(k -- ) { ans += mx[1] , x = ref[mp[1]]; while(x && !del[x]) update(pos[x] , last[x] , w[x] , 1 , n , 1) , del[x] = 1 , x = fa[x]; } printf("%lld\n" , ans); return 0; }