题解 CF671D 【Roads in Yusland】

# [Codeforces671D]Roads in Yusland [你真的不想进来看一看吗](https://www.cnblogs.com/xzyxzy/p/10478869.html) --- ## 题意 [luogu](https://www.luogu.org/problemnew/show/CF671D) 给定以1为根的一棵树，有$m$条直上直下的有代价的链，求选一些链把所有边覆盖的最小代价。若无解输出`-1` $n\le 3*10^5$ ## 题解 这题有一些DP做法，这里不再赘述了。 首先你得知道[线性规划的对偶](https://www.cnblogs.com/xzyxzy/p/10478865.html)。 式子是这样的$max\{c^Tx|Ax\le b\}=min\{b^Ty|A^Ty\ge c\}$ 强行往上面套（右式）： - $c$为全1列向量，长度为$m$ - $y$为01列向量，长度为$m$，表示每条链选或不选 - $A^T$为长$n-1$、宽$m$的01矩阵，$A[i][j]$表示$i$这条边在不在第$j$条链中 - $b^T$为长为$m$的行向量，表示选每条链的代价 所以现在的问题就是要构造一个$x$使得左式最大。 那我们寻找左式的实际意义：给每条边标记一个权值$x$，使得每条链上的边的权值和不超过其代价。 感觉完全不是一个问题了对吧，但是确实他们答案相同。 为方便表述，这条边标记权值$x$记为这条边选了$x$次。 然后这是一个较为显然的贪心，从深到浅能选则选，用可并堆维护当前点到父亲这条边能选的最多次数。 ## 代码 ```cpp #include<iostream> #include<vector> #define pb push_back #define lc t[x].ch[0] #define rc t[x].ch[1] using namespace std; const int N=3e5+10; int n,m,cf[N],rt[N],dep[N],nod; long long Ans; vector<int> E[N],St[N]; struct mmp{int x,y,c;}A[N]; struct Heap{int ch[2],val,id,dis,tag;}t[N]; void Put(int x,int k) {t[x].tag+=k;t[x].val+=k;} void pushdown(int x) {int &v=t[x].tag;if(v) Put(lc,v),Put(rc,v),v=0;} int Merge(int x,int y) { if(!x||!y) return x+y; pushdown(x);pushdown(y); if(t[x].val>t[y].val) swap(x,y); rc=Merge(rc,y); if(t[lc].dis<t[rc].dis) swap(lc,rc); t[x].dis=t[lc].dis+1; return x; } int Del(int x) {return Merge(lc,rc);} void dfs(int x,int fr) { dep[x]=dep[fr]+1; for(auto R:E[x]) if(R!=fr) dfs(R,x),rt[x]=Merge(rt[x],rt[R]),cf[x]+=cf[R]; if(!cf[x]&&x>1) puts("-1"),exit(0); for(auto P:St[x]) t[++nod].val=A[P].c,t[nod].id=P,rt[x]=Merge(rt[x],nod); while(dep[A[t[rt[x]].id].y]>=dep[x]) rt[x]=Del(rt[x]); if(rt[x]) Ans+=t[rt[x]].val,Put(rt[x],-t[rt[x]].val); } int main() { cin>>n>>m; for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),E[x].pb(y),E[y].pb(x); for(int i=1,x,y,c;i<=m;i++) { scanf("%d%d%d",&x,&y,&c); St[x].pb(i);cf[x]++;cf[y]--; A[i]=(mmp){x,y,c}; } dfs(1,0); cout<<Ans<<endl; } ```