P6419 [COCI2014-2015#1] Kamp 题解

· · 题解

被 89L 老师的神秘做法深深地震撼了，用这篇文章来表达我的膜拜之意。

首先要知道本质上是在维护俩东西：

后者换根，线段树都很好做，不多赘述。

维护联通块边权之和，传统的做法是换根、分讨，不过 89L 老师提出可以考虑每条边的贡献。

我们发现，对于一条边 u\to v：

考虑维护这个操作，显然利用 DFN 序可以快速的找到区间解决问题，差分就行，这一档就做完了。

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define Ls(x) (x<<1)
#define Rs(x) (x<<1|1)
using namespace std;
const LL N=1e6+5;
const LL Inf=1e15;
struct Edge{LL To,W;};
LL n,K,Sz[N],S[N],F[N],g[N],D[N],Dfn[N],TOT,Lz[N<<2],Mx[N<<2];
vector<Edge>G[N];
inline void Add(LL l,LL r,LL x){F[l]+=x,F[r+1]-=x;}
inline void Down(LL Rt)
{
    LL k=Lz[Rt];
    Lz[Rt]=0;
    Mx[Ls(Rt)]+=k,Mx[Rs(Rt)]+=k;
    Lz[Ls(Rt)]+=k,Lz[Rs(Rt)]+=k;
}
inline void Up(LL Rt){Mx[Rt]=max(Mx[Ls(Rt)],Mx[Rs(Rt)]);};
void Upd(LL Rt,LL L,LL R,LL x,LL y)
{
    if(L==R)
    {
        Mx[Rt]=y;
        return;
    }
    Down(Rt);
    LL Mid=L+R>>1;
    if(x<=Mid)Upd(Ls(Rt),L,Mid,x,y);
    else Upd(Rs(Rt),Mid+1,R,x,y);
    Up(Rt);
}
void Upd(LL Rt,LL L,LL R,LL l,LL r,LL x)
{
    if(R<l||r<L)return;
    if(l<=L&&R<=r)
    {
        Lz[Rt]+=x,Mx[Rt]+=x;
        return;
    }
    Down(Rt);
    LL Mid=L+R>>1;
    Upd(Ls(Rt),L,Mid,l,r,x);
    Upd(Rs(Rt),Mid+1,R,l,r,x);
    Up(Rt);
}
void Dfs(LL x,LL f)
{
    //cout<<x<<endl;
    Sz[x]=1,Dfn[x]=++TOT;
    if(S[x]==1)Upd(1,1,n,Dfn[x],D[x]);
    else Upd(1,1,n,Dfn[x],-Inf);
    for(Edge i:G[x])
    {
        if(i.To==f)continue;
        D[i.To]=D[x]+i.W;
        Dfs(i.To,x);
        S[x]+=S[i.To],Sz[x]+=Sz[i.To];
    }
    for(Edge i:G[x])
    {
        if(i.To==f)continue;
    //  cout<<x<<"->"<<i.To<<endl;
        if(S[i.To])Add(1,n,i.W),Add(Dfn[i.To],Dfn[i.To]+Sz[i.To]-1,-i.W);
        if(S[i.To]!=K)Add(Dfn[i.To],Dfn[i.To]+Sz[i.To]-1,i.W);
    }
}
void Work(LL x,LL f)
{
    g[x]=Mx[1];
    for(Edge i:G[x])
    {
        if(i.To==f)continue;
        Upd(1,1,n,1,n,i.W);
        Upd(1,1,n,Dfn[i.To],Dfn[i.To]+Sz[i.To]-1,-2*i.W);
        Work(i.To,x);
        Upd(1,1,n,1,n,-i.W);
        Upd(1,1,n,Dfn[i.To],Dfn[i.To]+Sz[i.To]-1,2*i.W);
    }
}
int main()
{
    scanf("%lld%lld",&n,&K);
    for(LL i=1,x,y,z;i<n;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        G[x].pb({y,z}),G[y].pb({x,z});
    }
    for(LL i=1,x;i<=K;i++)
    {
        scanf("%lld",&x);
        S[x]++;
    }
    Dfs(1,0);
    for(int i=1;i<=n;i++)F[i]+=F[i-1];
    Work(1,0);
    for(int i=1;i<=n;i++)printf("%lld\n",2*F[Dfn[i]]-g[i]);
}