調(diào)了半天居然還能是線段樹(shù)寫(xiě)錯(cuò)了，藥丸

　　這題大概是類似一個(gè)樹(shù)形DP的東西。設(shè)$dp[i]$為修完i這棵子樹(shù)的最小代價(jià)，假設(shè)當(dāng)前點(diǎn)為$x$，但是轉(zhuǎn)移的時(shí)候我們不知道子節(jié)點(diǎn)到底有沒(méi)有一條越過(guò)$x$的路。如果我們枚舉每條路去轉(zhuǎn)移，會(huì)發(fā)現(xiàn)這條路沿線上的其他子樹(shù)的答案難以統(tǒng)計(jì)，那怎么辦呢，我們可以讓這條路向上回溯的時(shí)候順便記錄一下，于是有$val[i]$表示必修i這條路，并且修完當(dāng)前子樹(shù)的最小代價(jià)。

　　則有轉(zhuǎn)移$dp[x]=min(val[j])$，且$j$這條路必須覆蓋$x$。

　　$val[i]=(\sum dp[son])-dp[sonx]+val[i]$，且$i$這條路必須覆蓋$sonx$。

　　轉(zhuǎn)移用線段樹(shù)來(lái)維護(hù)就好，至于怎么判斷某條路是否覆蓋兩個(gè)點(diǎn)，只要遞歸到某條路的起點(diǎn)的時(shí)候把$val[i]$改為$(\sum dp[son])+cost[i]$，遞歸到某條路終點(diǎn)的時(shí)候把$val[i]$改為$inf$就好了。

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010; const ll inf=1e15; struct poi{ll sum, delta;}tree[maxn<<2]; struct tjm{int too, pre;}e[maxn<<1], e2[maxn<<1], e3[maxn<<1]; struct qaq{int x, y, cost, pos;}q[maxn]; ll dp[maxn]; int n, m, x, y, tot, tot2, tot3, tott, l[maxn], r[maxn], last[maxn], last2[maxn], last3[maxn]; inline void read(int &k) {int f=1; k=0; char c=getchar();while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();k*=f; } inline void add(int x, int y){e[++tot]=(tjm){y, last[x]}; last[x]=tot;} inline void add2(int x, int y){e2[++tot2]=(tjm){y, last2[x]}; last2[x]=tot2;} inline void add3(int x, int y){e3[++tot3]=(tjm){y, last3[x]}; last3[x]=tot3;} inline void up(int x) {tree[x].sum=min(tree[x<<1].sum, tree[x<<1|1].sum);} inline void addone(int x, int l, int r, ll delta) {tree[x].delta=min(inf, tree[x].delta+delta);tree[x].sum=min(inf, tree[x].sum+delta); } inline void down(int x, int l, int r) {int mid=(l+r)>>1;addone(x<<1, l, mid, tree[x].delta);addone(x<<1|1, mid+1, r, tree[x].delta);tree[x].delta=0; } void build(int x, int l, int r) {if(l==r) {tree[x].sum=inf; return;}int mid=(l+r)>>1;build(x<<1, l, mid); build(x<<1|1, mid+1, r);up(x); } void update(int x, int l, int r, int cx, ll delta) {if(l==r) {tree[x].sum=delta; return;}down(x, l, r);int mid=(l+r)>>1;if(cx<=mid) update(x<<1, l, mid, cx, delta);else update(x<<1|1, mid+1, r, cx, delta);up(x); } void change(int x, int l, int r, int cl, int cr, ll delta) {if(cl>cr) return;if(cl<=l && r<=cr) {addone(x, l, r, delta); return;}down(x, l, r);int mid=(l+r)>>1;if(cl<=mid) change(x<<1, l, mid, cl, cr, delta);if(cr>mid) change(x<<1|1, mid+1, r, cl, cr, delta);up(x); } ll query(int x, int l, int r, int cl, int cr) {if(cl>cr) return inf;if(cl<=l && r<=cr) return tree[x].sum;down(x, l, r);int mid=(l+r)>>1; ll ans=inf;if(cl<=mid) ans=query(x<<1, l, mid, cl, cr);if(cr>mid) ans=min(ans, query(x<<1|1, mid+1, r, cl, cr));return ans; } void dfs1(int x, int fa) {l[x]=++tott;for(int i=last[x], too;i;i=e[i].pre)if((too=e[i].too)!=fa) dfs1(too, x);r[x]=tott; } inline int find(int x) {int l=1, r=m+1;while(l<r){int mid=(l+r)>>1;if(q[mid].pos>=x) r=mid;else l=mid+1; }return l; } void dfs2(int x, int fa) {ll sum=0;for(int i=last[x], too;i;i=e[i].pre)if((too=e[i].too)!=fa) dfs2(too, x), sum=min(inf, sum+dp[too]);if(x==1) {dp[1]=sum; return;}for(int i=last2[x];i;i=e2[i].pre) update(1, 1, m, e2[i].too, min(inf, q[e2[i].too].cost+sum));for(int i=last3[x];i;i=e3[i].pre) update(1, 1, m, e3[i].too, inf);for(int i=last[x], too;i;i=e[i].pre)if((too=e[i].too)!=fa) change(1, 1, m, find(l[too]), find(r[too]+1)-1, sum-dp[too]);dp[x]=query(1, 1, m, find(l[x]), find(r[x]+1)-1); } inline bool cmp(qaq a, qaq b){return a.pos<b.pos;} int main() {read(n); read(m); build(1, 1, m);for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);dfs1(1, 0); for(int i=1;i<=m;i++) read(q[i].x), read(q[i].y), read(q[i].cost), q[i].pos=l[q[i].x];sort(q+1, q+1+m, cmp); q[m+1].pos=n+1;for(int i=1;i<=m;i++) add2(q[i].x, i), add3(q[i].y, i);dfs2(1, 0);if(dp[1]>=inf) return puts("-1"), 0;printf("%lld\n", dp[1]); } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/Sakits/p/8085598.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 671D. Roads in Yusland（树形DP+线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。