题解:　首先　考虑一个贪心策略是　每次选取必然是　每个点到根的路径和的最大值的点　然后考虑去掉这个点的影响　影响子树的价值　这样的话我们就可以dfs序维护子树了　去掉这个点只要把这点的权值在其子树中减去　然后维护到根的最大值和位置　线段树即可　然后顺着根往上爬找到第一个在之前被访问的点即可(因为这个点被访问　他的祖先也必然被访问　做k次得出答案即可

#include 
     
      const int MAXN=2e5+10;#define ll long longusing namespace std;struct FastIO{    static const int S=200;    int wpos;    char wbuf[S];    FastIO():wpos(0){}    inline int xchar()    {        static char buf[S];        static int len=0,pos=0;        if(pos==len) pos=0,len=fread(buf,1,S,stdin);        if(pos==len) exit(0);        return buf[pos++];    }    inline int read()    {        int s=1,c=xchar(),x=0;        while(c<=32) c=xchar();        if(c=='-') s=-1,c=xchar();        for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';        return x*s;    }    ~FastIO()    {        if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;    }}io;int n,k;int a[MAXN];bool vis[MAXN];vector
      
       vec[MAXN];int fa[MAXN],p[MAXN],fp[MAXN],cnt;ll dis[MAXN];int num[MAXN];void dfs(int v,int pre){	p[v]=++cnt;fp[p[v]]=v;fa[v]=pre;dis[v]=dis[pre]+a[v];num[v]=1;	for(int i=0;i
       
        >1;	built(rt<<1,l,mid);	built(rt<<1|1,mid+1,r);	up(rt);}void update(int rt,int l,int r,int ql,int qr,ll vul){	if(ql<=l&&r<=qr){maxx[rt]+=vul;flag[rt]+=vul;return ;}	int mid=(l+r)>>1;	push(rt);	if(ql<=mid)update(rt<<1,l,mid,ql,qr,vul);	if(qr>mid)update(rt<<1|1,mid+1,r,ql,qr,vul);	up(rt);}int main(){	n=io.read();k=io.read();	for(int i=1;i<=n;i++)a[i]=io.read();	int u,v;	for(int i=1;i
        
         0){update(1,1,n,p[t1],p[t1]+num[t1]-1,-a[t1]);vis[t1]=1;cnt--;t1=fa[t1];}		if(cnt==0)break;	}	printf("%lld\n",ans);}
        
       
      
     

 

3252: 攻略

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 967  Solved: 461

[][][]

Description

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX

半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状

结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同

时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

Input

第一行两个正整数n,k

第二行n个正整数，表示每个场景的价值

以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）

保证场景1为根节点

n<=200000，1<=场景价值<=2^31-1

Output

输出一个整数表示答案

Sample Input

5 2

4 3 2 1 1

1 2

1 5

2 3

2 4

Sample Output

10