Description
一颗树n个点，n-1条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有K个人（分布在K个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这K个人分别送回去。
请你回答，对于i=1~n，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。
（注：一个车可以同时乘坐k个人）
HINT
【数据规模】
K <= N <= 500000
1 <= x,y <= N, 1 <= z <= 1000000
Solution
首先一定是一个二次扫描+换根
我的方法：
考虑到，进入一个子树，一定是把这个子树的人都送完再回到子树的根，或者不回到根，就结束了。
所以，套路地，令f[i]表示，以i为根的子树，把所有的关键点遍历到，再回到i的最小花费。
g[i]表示，以i为根的子树，把所有关键点遍历到，不回到i的最小花费。
以1号点为根，
直接树形dp一次可以求出。
注意，子树里没有关键点的f，g都是0
然后考虑换根
1号点的答案已经得到，计入ans[1]
换根的时候，fa就是x之前的根，现在x要变成根，
但是，fa的f，g可能进到了x的子树。
所以，设hf[i]为不经过当前根所在的子树，遍历其他关键点，回到i的最小时间。
hg[i]表示，........................,..........,不回到i的最小时间（省略重复内容）
oh[i]表示，除了当前根所在子树外，其他子树里（包括自己）有没有关键点。
每次，更新fa的hg，hf，oh
然后，用x的f，g和fa的hg，hf，oh确定ans[x]
细节很多，找std对拍了半天：
1.x的fa找子树的时候，可能找到fa的father，就要用hf[father[fa]]了。
2.第一遍dfs时，可能x是叶子，可能x是关键点，但是子树里没有，可能x及其子树都没有关键点，这些情况f，g都是0
3.换根的时候，考虑x的fa的hg，hf，也要像上面一样考虑。
但是，每次换根的时候，要遍历fa的所有儿子。
菊花图直接T的飞起~~~
（但是bzoj数据水）
Code
#include<bits/stdc++.h> using namespace std; const int N=500000+10; typedef long long ll; const ll inf=(1LL*1<<62); int n,m; struct node{ int nxt,to,val; }e[2*N]; int hd[N],cnt; void add(int x,int y,int z){ e[++cnt].nxt=hd[x]; e[cnt].val=z; e[cnt].to=y; hd[x]=cnt; } ll dis[N]; bool exi[N]; bool has[N]; ll f[N],g[N]; ll hf[N],hg[N]; bool oh[N]; ll ans[N]; int ff[N]; void dfs(int x,int fa,ll d){ dis[x]=d; ll sumf=0; bool fl=false;//fl记录是否是叶子 bool bla=false;//bla记录是否有一个子树里有关键点（不包括自己） for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; fl=true; dfs(y,x,d+e[i].val); ff[y]=x; has[x]|=has[y]; if(has[y]){ bla=true; sumf+=f[y]+e[i].val*2; } } if(!has[x]||!fl||!bla) { f[x]=g[x]=0;return; } f[x]=sumf; g[x]=inf; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; if(has[y]){ ll now=sumf-f[y]+g[y]-e[i].val; g[x]=min(g[x],now); } } } void sol(int x,int fa){ if(x!=1){ ll sumf=0; ll valf=0; oh[fa]=0;//oh[fa]记得清0，因为可能这个fa会作为多个son的father if(exi[fa]) oh[fa]=true; for(int i=hd[fa];i;i=e[i].nxt){ int y=e[i].to; if(y==x) { valf=e[i].val; continue; } else if(y==ff[fa]){ if(oh[y]){ oh[fa]=1; sumf+=hf[y]+2*e[i].val; } } else{ if(has[y]){ oh[fa]=1; sumf+=f[y]+2*e[i].val; } } } hf[fa]=sumf; hg[fa]=inf; if(oh[fa]){ bool son=false,bla=false;//son记录除了x是否有儿子。bla同上含义 for(int i=hd[fa];i;i=e[i].nxt){ int y=e[i].to; if(y==x) continue; son=true; if(y==ff[fa]){ if(oh[y]){ bla=true; ll now=sumf-hf[y]+hg[y]-e[i].val; hg[fa]=min(hg[fa],now); } } else if(has[y]){ bla=true; ll now=sumf-f[y]+g[y]-e[i].val; hg[fa]=min(hg[fa],now); } } if(!son||!bla) hf[fa]=0,hg[fa]=0; } else{ hf[fa]=0; hg[fa]=0; } ll ansf=f[x],ansg=inf;//注意ansg=inf，当有子树至少存在一个关键点，ansg就可以得到正确答案 if(oh[fa]) ansf+=sumf+2*valf; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa){ if(oh[fa]){ ll now=ansf-sumf+hg[fa]-e[i].val; ansg=min(ansg,now); } } else{ if(has[y]){ ll now=ansf-f[y]+g[y]-e[i].val; ansg=min(ansg,now); } } } ans[x]=ansg; } if(exi[x]&&m==1){//全场只有一个关键点，特判，就是0了 ，否则由于ansg的锅，就成了inf ans[x]=0; } for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; sol(y,x); } } int main() { scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<=n-1;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); }int t; for(int i=1;i<=m;i++){ scanf("%d",&t); exi[t]=has[t]=1; } dfs(1,0,0); ans[1]=g[1]; sol(1,0); for(int i=1;i<=n;i++){ printf("%lld ",ans[i]); } return 0; }
代码丑，而且会被hack掉。
正解：
以某个关键点为根，
对于所有的关键点建一棵虚树tree，所有的权值和是sum
虚树内的节点x的答案，就是sum*2再减去x往下最长链的长度。
虚树外的节点x的答案（一定是虚树某个节点的儿子），就是进入这个虚树的距离，加上进入点在虚树里的答案。
换根还是要考虑x的fa的最长链可能经过x。
所以，对于每个点记录一个最长链，一个次长链，（两个链从不同的儿子下去）和它们是从节点的哪一个儿子dp得到的。
rt从fa换到x，
如果fa的最长链不经过x，当前的最长链就是，fa的最长链加上x到fa的边权。
如果fa的最长链经过x，当前的最长链就是，x的最长链，和边权加上fa的次长链取个max
如果fa没有次长链，即fa只有x一个儿子，那么就是x的最长链和边权取个max