Codeforces 671D. Roads in Yusland(树形DP+线段树)

时间:2021-09-25 11:38:45

  调了半天居然还能是线段树写错了,药丸

  这题大概是类似一个树形DP的东西。设$dp[i]$为修完i这棵子树的最小代价,假设当前点为$x$,但是转移的时候我们不知道子节点到底有没有一条越过$x$的路。如果我们枚举每条路去转移,会发现这条路沿线上的其他子树的答案难以统计,那怎么办呢,我们可以让这条路向上回溯的时候顺便记录一下,于是有$val[i]$表示必修i这条路,并且修完当前子树的最小代价。

  则有转移$dp[x]=min(val[j])$,且$j$这条路必须覆盖$x$。

  $val[i]=(\sum dp[son])-dp[sonx]+val[i]$,且$i$这条路必须覆盖$sonx$。

  转移用线段树来维护就好,至于怎么判断某条路是否覆盖两个点,只要递归到某条路的起点的时候把$val[i]$改为$(\sum dp[son])+cost[i]$,递归到某条路终点的时候把$val[i]$改为$inf$就好了。

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