Bzoj-3252: 攻略（贪心+DFS序+线段树）

题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3252

（其实我也在看只有神知道的世界，所以就来写这道题了。。。）

这道题解法题目里面都说了一半了QaQ...首先，很容易可以确定每次贪心取最大的一条路径，然后修改权值的正确性，（反证法：假如该贪心不正确，则存在两条路径p1,p2,权值和s(p1)>s(p2),先取p2比先取p1更优，那么，如果当前取的是最后一条路径，那么明显这个情况不成立，如果不是，则先取p2再取p1等效于先取p1再取p2,所以贪心成立）。

实现方法：

暴力当然TLE，我们可以把该树处理成DFS序，每个节点拆成在DFS中入栈的位置和出栈的位置，如，样例的一个DFS序就是: 1 2 3 3 4 4 2 5 5 1

然后，对于某个节点，在第一次出现的位置+w[i],最后出现的位置-w[i],然后进行一次求和sum[i]=sigma(a[j])(0<j<=i),那么，每次取最大的前缀和恰好就是最大的路径和。

修改：考虑到某个节点的权值变动，会影响到DFS序列中的后面的所有前缀和，所以每次修改时就用带懒惰标记的线段树来维护就可以了。

代码（记得开long long）:

（速度还是一如既往的渣:)

e61190ef76c6a7ef0d2e5a3cfffaaf51f3de66a4.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 200010
#define AddEdge(s,t) Add(s,t),Add(t,s)
#define L(t) T[t].l
#define R(t) T[t].r
#define D(t) T[t].delta
#define M(t) T[t].Max
#define Mm(t) T[t].maxm
struct edge{
    int t;
    edge *next;
    edge (){
        next=NULL;
    }
}*head[MAXN];
void Add(int s,int t){
    edge *p=new(edge);
    p->t=t,p->next=head[s];
    head[s]=p;
}
int fir[MAXN],las[MAXN],fat[MAXN],n,k;
long long sum[MAXN*2],w[MAXN];
int c[MAXN*2];
bool f[MAXN];
int Index=0;
void dfs(int v){
    f[v]=false;
    sum[fir[v]=++Index]=w[v];
    c[Index]=v;
    for(edge *p=head[v];p;p=p->next)if(f[p->t]){
        fat[p->t]=v;
        dfs(p->t);
    }
    sum[las[v]=++Index]=-w[v];
    c[Index]=v;
}
struct node{
    int l,r,maxm;
    long long Max,delta;
    node (){
        delta=0;
    }
} T[MAXN*10];
void pushdown(int t){
    if(D(t)){
        M(t)+=D(t);
        if(L(t)<R(t)){
            D(t<<1)+=D(t),D((t<<1)^1)+=D(t);
        }
        D(t)=0;
    }
}
void update(int t){
    pushdown(t);
    if(L(t)<R(t)){
        pushdown(t<<1),pushdown((t<<1)^1);
        if(M(t<<1)>M((t<<1)^1)){
            M(t)=M(t<<1),Mm(t)=Mm(t<<1);
        }else{
            M(t)=M((t<<1)^1),Mm(t)=Mm((t<<1)^1);
        }
    }
}
void Build(int l,int r,int t){
    L(t)=l,R(t)=r;
    if(l==r){
        M(t)=sum[l],Mm(t)=l;
        return;
    }
    int mid=(l+r)>>1;
    Build(l,mid,t<<1),Build(mid+1,r,(t<<1)^1);
    update(t);
}
void Change(int l,int r,int t,long long del){
    if(L(t)==l&&R(t)==r){
        D(t)+=del;
        pushdown(t);
        return;
    }
    pushdown(t);
    int mid=(L(t)+R(t))>>1;
    if(mid>=r) Change(l,r,t<<1,del)  
    ;  else if(mid<l) Change(l,r,(t<<1)^1,del)
    ;  else Change(l,mid,t<<1,del),Change(mid+1,r,(t<<1)^1,del);
    update(t);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i++<n;) scanf("%lld",&w[i]);
    memset(head,0,sizeof(head));
    for(int i=0;i++<n-1;){
        int s,t;
        scanf("%d%d",&s,&t);
        AddEdge(s,t);
    }
    memset(f,true,sizeof(f));
    fat[1]=0;
    sum[0]=0;
    dfs(1);
    for(int i=0;i++<2*n;) sum[i]+=sum[i-1];
    Build(1,2*n,1);
    memset(f,true,sizeof(f));
    f[0]=false;
    long long ans=0;
    while(k--){
        ans+=M(1);
        int v=c[Mm(1)];
        while(f[v]){
            f[v]=false;
            Change(fir[v],2*n,1,-w[v]);
            Change(las[v],2*n,1,w[v]);
            v=fat[v];
        }
    }
    printf("%lld\n",ans);
    return 0;
}