P6419 题解

· · 题解

为什么都用dp?

可以直接深搜+宽搜解决啊。

考虑一个弱化版的问题:

如果是还要回到聚会点要怎么做？

先通过树上差分+深搜，我们可以处理出所有关键点两两之间的路径交形成的一个子图（其实是一个更小的树），下文子图指的就是这个图，但同时你也可以称其为子树(?)。

以样例1为例：

标红的边就是我们处理出来的子图。

同时做一遍dfs/bfs，我们还可以处理出来其他的点到这个子图的最小距离，在样例中 dis[6]=2 , dis[5]=1 ,其他为 0 。

此时答案就很显然了，节点 x 答案就是 (子图上边权和+dis[x]) \times 2 。

为什么？

先考虑该子图上一点，使用异象石中我们得到的二级结论，遍历这些关键节点需要的最小距离就是 将所有点按照dfs序排序之后每一个点和后面一个点的距离和 ，特别的，还要加上第一个点和最后一个点的距离。

那么子图外一点呢？很显然，从子图外一点肯定要先走到子图那里，然后就转化为上一段的子问题了。

这个很简单，树上差分并深搜和宽搜都是 O(n) 的，打差分时如果书上 lca 用 st 表的 O(1) 做法应该可以做到 O(n) , 但是作者太懒了就只写了树剖 。

如果不需要回到原点呢？

在上一问的基础上，回答每一个点时，我们只需要找到这个子图上距离该点最远的点并将他们的距离减去即可。

这个应该不用证吧

那么怎么找这个最远距离呢？我们先处理出这个子图的直径两端点，然后判断该点和两端点最大值即可， 是的，到该点最远一点必然是直径端点，这个结论在任意正边权以及点不在该子图上时仍旧成立。

其实这个时候答案已经解决了，额外讲一下怎么 O(nlogn) (理论 O(n) ，但是作者懒 )求该子图的直径。

考虑递推，如果我们已经知道了前 n-1 个点的直径及其端点，那么我们只要知道新的点到两个端点的距离和原直径的大小关系即可。

时间复杂度 O(nlogn) ，复杂度瓶颈在于树上求 lca ，如果使用 st 表 O(1) 查询可以做到 O(n)

#include<bits/stdc++.h>

#define int long long
#define mod 998244353
#define maxn 500005

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

struct edge{
    int to;
    int val;
    int next;
}e[2*maxn];

int e_cnt=1,head[maxn];

void add(int u,int v,int w){
    e[e_cnt].to=v;
    e[e_cnt].val=w;
    e[e_cnt].next=head[u];
    head[u]=e_cnt++;
}

int n,k;
int depth[maxn],cnt[maxn],sz[maxn],son[maxn],f[maxn];
int dfs_cnt=1;
int root[maxn],mapping[maxn],q_map[maxn];

int res=0;
pair<int,int> nd;int d=0;
vector<int> v;

void dfs1(int x,int fa){
    f[x]=fa;cnt[x]=cnt[fa]+1;
    sz[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        depth[v]=depth[x]+e[i].val;
        dfs1(v,x);
        sz[x]+=sz[v];
        if(sz[son[x]]<sz[v])son[x]=v;
    }
}

void dfs2(int x,int rt){
    root[x]=rt;
    mapping[dfs_cnt]=x;
    q_map[x]=dfs_cnt++;
    if(son[x])dfs2(son[x],rt);
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==f[x]||v==son[x])continue;
        dfs2(v,v);
    }
}

int lca(int u,int v){
    while(root[u]!=root[v]){
        if(cnt[root[u]]<cnt[root[v]])swap(u,v);
        u=f[root[u]];
    }
    if(cnt[u]<cnt[v])return u;
    return v;
}

int dist(int u,int v){
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}

bool cmp(int a,int b){
    return q_map[a]<q_map[b];
}

int click[maxn];

void dfs3(int x){
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==f[x])continue;
        dfs3(v);
        click[x]+=click[v];
    }
}

queue<int> q;
bool visited[maxn];
int dis[maxn];

signed main(){

    n=read();k=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();;
        add(u,v,w);add(v,u,w);
    }
    dfs1(1,0);dfs2(1,1);
    for(int i=1;i<=k;i++){
        int x=read();
        if(nd.first==0){
            nd.first=x;
        }else if(nd.second==0){
            nd.second=x;
            d=dist(nd.first,x);
        }else{
            int d1=dist(nd.first,x),d2=dist(nd.second,x);
            if(d1>=d2&&d1>d){
                nd.second=x;
                d=d1;
            }else if(d2>=d1&&d2>d){
                nd.first=x;
                d=d2;
            }
        }
        v.push_back(x);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++){
        int x=v[i],y=v[(i+1)%v.size()];
        res=res+dist(x,y);
        click[x]++;click[y]++;
        int LCA=lca(x,y);
        click[LCA]--;click[f[LCA]]--;
    }
    dfs3(1);
    for(int i=1;i<=n;i++){
        if(click[i]){
            q.push(i);
            visited[i]=true;
            dis[i]=0;
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].next){
            int v=e[i].to;
            if(visited[v])continue;
            visited[v]=true;dis[v]=dis[x]+e[i].val;
            q.push(v);
        }
    }

    for(int i=1;i<=n;i++){
        int d1=dist(nd.first,i),d2=dist(nd.second,i);
        printf("%lld\n",res+2*dis[i]-max(d1,d2)); 
    }

    return 0;
}
/*
answer:subtree+2*dis-max_len
*/