建一个网站式系统,自贡彩灯制作公司,网站官网域名要多少钱,网站建设需要啥题意
一颗树 n n n 个点#xff0c; n − 1 n-1 n−1 条边#xff0c;经过每条边都要花费一定的时间#xff0c;任意两个点都是联通的。
有 k k k 个人#xff08;分布在 k k k 个不同的点#xff09;要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点…题意
一颗树 n n n 个点 n − 1 n-1 n−1 条边经过每条边都要花费一定的时间任意两个点都是联通的。
有 k k k 个人分布在 k k k 个不同的点要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发把这 K K K 个人分别送回去。
请你回答对于 i 1 ∼ n i1 \sim n i1∼n 如果在第 i i i 个点举行聚会司机最少需要多少时间把 k k k 个人都送回家。 1 ≤ k ≤ n ≤ 5 × 1 0 5 1 \le k \le n \leq 5\times 10^5 1≤k≤n≤5×105 1 ≤ x , y ≤ n 1 \le x,y \le n 1≤x,y≤n 1 ≤ z ≤ 1 0 8 1 \le z \le 10^8 1≤z≤108 。
思路
这是一道换根dp
直接计算从一个点出发经过所有家之后最后在一个点停下的最短路程是比较难的。但是可以维护从一个点出发再回到自己的最短路程减去该点到其中一个家的最长链那也是答案。
第一个dfs
经典地先用第一个dfs处理子树内信息。
用 v i s u vis_u visu标记 u u u是否为一个家 s v u sv_u svu表示 u u u子树内有多少有家之人。
令 g u g_u gu表示在 u u u子树内从 u u u出发走完所有有家之人再回到 u u u的最短距离那么在处理边 ( u , v ) (u,v) (u,v)边权为 w w w时有 g u 2 w ∑ v ∈ s o n u g v g_u2w\sum_{v\in son_u}g_v gu2wv∈sonu∑gv w w w要乘 2 2 2是因为要走来回。
那么到维护最长链了先维护子树内的最长链不过为了在第2次dfs中处理全局的最长链信息涉及到两个点 ( u , v ) (u,v) (u,v)的次序问题即 u u u成为 v v v子树内的一点还需要维护一个次长链来保证正确性。
令 D u D_u Du表示 u u u节点开始子树内最长链 s D u sD_u sDu表示 u u u节点开始子树内次长链可以用一个 n x u nx_u nxu记录该最长链上 u u u的下一个节点因为在最长链上任一节点 x x x子树的、由 x x x开始的最长链必然与 u u u开始的最长链重合
void dfs1(ll u,ll fa)
{if(vis[u])sv[u]1;for(int ihead[u];i;ie[i].next){ll ve[i].to,we[i].w;if(vfa)continue;dfs1(v,u);if(sv[v]){g[u]g[v]2*w;if(wD[v]D[u]){sD[u]D[u];D[u]wD[v];nx[u]v;}else if(wD[v]sD[u])sD[u]wD[v];}sv[u]sv[v];}
}第二个dfs
在第二个dfs中我们将处理整棵树内的信息了。
令 f u f_u fu表示在整棵树中从 u u u出发走完所有有家之人再回到自己的最短路程。
在第一个dfs中我们记录了 s v u sv_u svu表示 u u u子树内有多少有家之人对于一个节点 u u u和后继结点 v v v考虑利用 s v u sv_u svu或 s v v sv_v svv进行分类讨论 s v v k sv_vk svvk
那么和子树的情况没有区别也不必更新最长链、次长链了直接 f v g v f_vg_v fvgv即可。 s v v 0 sv_v0 svv0
那么说明 v v v的子树内没有人有家在第一次dfs时 u u u并没有往 v v v的方向更新。此处可以看作 u u u是在 v v v的子树内需要倒着用 u u u来更新 v v v。并且可以直接更新比大小都可以不需要qwq
其余情况 u u u和 v v v子树内都有有家之人。设最长链分布如图所示 设 w w w为边 ( u , v ) (u,v) (u,v)的边权
更新 D v D_v Dv
若 D u w ≥ D v D_uw \ge D_v Duw≥Dv且 n x u ≠ v nx_u \ne v nxuv即 v v v不在 u u u的原本的最长链上直接更新 D v D_v Dv若 n x u v nx_uv nxuv则不能更新。
若 s D u w ≥ D v sD_uw \ge D_v sDuw≥Dv并没有影响直接继承即可。
更新 s D v sD_v sDv
与上相同
void dfs2(ll u,ll fa)
{for(int ihead[u];i;ie[i].next){ll ve[i].to,we[i].w;if(vfa)continue;if(!sv[v])//v子树内无家倒着更新 {if(D[u]wD[v]){sD[v]D[v];D[v]D[u]w;f[v]f[u]2*w;} }else if(k-sv[v]0)f[v]g[v];else //更新D(v) {f[v]f[u];if(D[u]wD[v]nx[u]!v){sD[v]D[v];D[v]D[u]w;nx[v]u;}else if(sD[u]wD[v]){sD[v]D[v];D[v]sD[u]w;nx[v]u;}else if(D[u]wsD[v]nx[u]!v)sD[v]D[u]w;else if(sD[u]wsD[v])sD[v]sD[u]w;}dfs2(v,u);}
}代码
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N5e59;
ll n,k;
ll idx,head[N];
ll sv[N],vis[N],D[N],sD[N],nx[N],f[N],g[N];
//sv(u):u子树内总共多少有家之人
//D/sD(u):u起点最长次长链
//nx(u): 最长链上下一个节点
//g(u):u子树内走完所有有家之人回u的最短距离
//f(u):整棵树内走完所有有家之人回u的最短距离
struct edge
{ll to,next,w;
}e[N1];
void addedge(ll u,ll v,ll w)
{idx;e[idx].tov;e[idx].nexthead[u];e[idx].ww;head[u]idx;
}
void dfs1(ll u,ll fa)
{if(vis[u])sv[u]1;for(int ihead[u];i;ie[i].next){ll ve[i].to,we[i].w;if(vfa)continue;dfs1(v,u);if(sv[v]){g[u]g[v]2*w;if(wD[v]D[u]){sD[u]D[u];D[u]wD[v];nx[u]v;}else if(wD[v]sD[u])sD[u]wD[v];}sv[u]sv[v];}
}
void dfs2(ll u,ll fa)
{for(int ihead[u];i;ie[i].next){ll ve[i].to,we[i].w;if(vfa)continue;if(!sv[v])//v子树内无家倒着更新 {if(D[u]wD[v]){sD[v]D[v];D[v]D[u]w;f[v]f[u]2*w;} }else if(k-sv[v]0)f[v]g[v];else //更新D(v) {f[v]f[u];if(D[u]wD[v]nx[u]!v){sD[v]D[v];D[v]D[u]w;nx[v]u;}else if(sD[u]wD[v]){sD[v]D[v];D[v]sD[u]w;nx[v]u;}else if(D[u]wsD[v]nx[u]!v)sD[v]D[u]w;else if(sD[u]wsD[v])sD[v]sD[u]w;}dfs2(v,u);}
}
int main()
{scanf(%lld%lld,n,k);for(int i1;in;i){ll u,v,w;scanf(%lld%lld%lld,u,v,w);addedge(u,v,w);addedge(v,u,w);}for(int i1;ik;i){ll u;scanf(%lld,u);vis[u]1;}dfs1(1,0);f[1]g[1];dfs2(1,0);for(int i1;in;i)printf(%lld\n,f[i]-D[i]);return 0;
}
