正題

題目鏈接:https://jzoj.net/senior/#main/show/3919

---

題目大意

$n$個點$k$個需要到達的點，然后求每個點出發經過這些點的最短路徑。

---

解題思路

因為不用回去，答案就是以這點為根鏈接所有點的樹減去離這個點最遠點的距離。

我們用線段樹維護最遠點距離，然后換根。

對于轉移到一個節點，如果這個節點的子樹沒有任何必經點那么就加上這條邊的邊長，如果這個子樹包含所有必經點那么減去這條邊的邊長。

然后就搞定了此題。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define ll long long using namespace std; const ll N=510000; struct node{ll to,next,w; }a[N*2]; struct treenode{ll l,r,w,lazy; }; ll n,k,tot,ls[N],dep[N],dfn[N],rfn[N],ed[N],v[N],f[N],l[N],cnt,Z[N]; struct LineTree{treenode t[N*4];void Build(ll x,ll l,ll r){t[x].l=l;t[x].r=r;if(l==r){if(Z[dfn[l]])t[x].w=dep[dfn[l]];else t[x].w=-2147483647/3;return;}ll mid=(l+r)/2;Build(x*2,l,mid);Build(x*2+1,mid+1,r);t[x].w=max(t[x*2].w,t[x*2+1].w);}void Downdata(ll x){if(t[x].lazy){t[x*2].lazy+=t[x].lazy;t[x*2+1].lazy+=t[x].lazy;t[x*2].w+=t[x].lazy;t[x*2+1].w+=t[x].lazy;t[x].lazy=0;}}void Change(ll x,ll l,ll r,ll num){if(t[x].l==l&&t[x].r==r){t[x].w+=num;t[x].lazy+=num;return;}Downdata(x);ll mid=(t[x].l+t[x].r)/2;if(r<=mid) Change(x*2,l,r,num);else if(l>mid) Change(x*2+1,l,r,num);else Change(x*2,l,mid,num),Change(x*2+1,mid+1,r,num);t[x].w=max(t[x*2].w,t[x*2+1].w);} }Tree; void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } ll dfs(ll x,ll fa) {rfn[x]=++cnt;dfn[cnt]=x;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;dep[y]=dep[x]+a[i].w;v[x]+=dfs(y,x);if(v[y])f[1]+=a[i].w;}ed[x]=cnt;return v[x]; } void dp(ll x,ll fa) {l[x]=Tree.t[1].w-1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;Tree.Change(1,1,n,a[i].w);Tree.Change(1,rfn[y],ed[y],-2*a[i].w);f[y]=f[x]+(!v[y])*a[i].w-(!(k-v[y]))*a[i].w;dp(y,x);Tree.Change(1,1,n,-a[i].w);Tree.Change(1,rfn[y],ed[y],2*a[i].w);} } int main() {scanf("%lld%lld",&n,&k);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(y,x,w);addl(x,y,w);}for(ll i=1;i<=k;i++){ll x;scanf("%lld",&x);Z[x]++;v[x]++;}dep[1]=1;dfs(1,1);Tree.Build(1,1,n);dp(1,0);for(ll i=1;i<=n;i++)printf("%lld\n",f[i]*2-l[i]); }

總結

以上是生活随笔為你收集整理的jzoj3919-志愿者【换根法,线段树,树形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。