Liveddd's Blog

愛にできることはまだあるかい

CF671D Roads in Yusland

发表于 更新于 分类于
本文字数： 4.2k 阅读时长 ≈ 9 分钟

线段树合并优化 DP。

考虑与 NOI2020 D1T2 命运 类似的方法，设计状态 $f_{x,i}$ 为以 $x$ 为根的子树中的边全部被覆盖，并且被覆盖的路径向上延伸至深度为 $i$ 的节点，所需要的最小花费。状态转移方程：$f_{x,i}=f_{x,i}+ \min_{j\ge i} {f_{y,j},f_{y,i}}+\min_{j\ge i}{f_{x,j}}$。这个方程中两边状态都与下标 $i$ 相同 ，并且信息也是线段树好维护的，于是可以用线段树合并来优化。

注意一些细节。（笔者因为不咋写动态开点误将 ql,qr 写成 l,r 调了将近一天，敲个警钟）。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long 
using namespace std;
const int N=3e5+10;
const int ll INF=1e16;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

struct Node
{
    int lc,rc;
    ll val,tag;
}tr[N*20];
struct Edge
{
    int v,w;
};
int n,m;
int tot,head[N],ver[N<<1],ne[N<<1];
int cnt,rt[N],d[N];
int top,sta[N*20];
vector<Edge>vec[N];
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
inline void del(int x)
{
    sta[++top]=x;
    tr[x].lc=tr[x].rc=0;
    tr[x].val=INF,tr[x].tag=0;
}
inline int newnode()
{
    if(top)return sta[top--];
    tr[++cnt].val=INF;
    return cnt;
}
inline void pushup(int x)
{
    tr[x].val=min(tr[tr[x].lc].val,tr[tr[x].rc].val);
}
inline void update(int x,ll k)
{
    tr[x].val+=k,tr[x].tag+=k;
    tr[x].val=min(tr[x].val,INF);
    tr[x].tag=min(tr[x].tag,INF);
}
inline void pushdown(int x)
{
    if(!tr[x].tag)return ;
    update(tr[x].lc,tr[x].tag);
    update(tr[x].rc,tr[x].tag);
    tr[x].tag=0;
}
void modify(int &x,int l,int r,int pos,ll k)
{
    if(!x)x=newnode();
    if(l==r)
    {
        tr[x].val=min(tr[x].val,k);
        return ;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(pos<=mid)modify(tr[x].lc,l,mid,pos,k);
    else modify(tr[x].rc,mid+1,r,pos,k);
    pushup(x);
}
ll query(int x,int l,int r,int ql,int qr)
{
    if(!x||(l>=ql&&r<=qr))return tr[x].val;
    pushdown(x);
    int mid=l+r>>1;
    ll res=INF;
    if(ql<=mid)res=min(res,query(tr[x].lc,l,mid,ql,qr));
    if(qr>mid)res=min(res,query(tr[x].rc,mid+1,r,ql,qr));
    return res;
}
int merge(int x,int y,int l,int r,ll resx,ll resy)
{
    if(!x&&!y)return 0;
    if(!x)return update(y,resx),y;
    if(!y)return update(x,resy),x;
    if(l==r)
    {
        tr[x].val=min({tr[x].val+resy,tr[y].val+resx,INF});
        del(y);
        return x;
    }
    pushdown(x),pushdown(y);
    int mid=l+r>>1;
    tr[x].lc=merge(tr[x].lc,tr[y].lc,l,mid,resx,resy);
    tr[x].rc=merge(tr[x].rc,tr[y].rc,mid+1,r,resx,resy);
    del(y);
    pushup(x);
    return x;
}
void dfs(int x,int fa)
{
    bool flag=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        flag=1,d[y]=d[x]+1;
        dfs(y,x);
        if(!rt[x])
        {
            rt[x]=rt[y];
            continue;
        }
        ll resx=query(rt[x],1,n,1,d[x]),resy=query(rt[y],1,n,1,d[x]);
        rt[x]=merge(rt[x],rt[y],1,n,resx,resy);
    }
    if(!flag)modify(rt[x],1,n,d[x],0);
    ll res=query(rt[x],1,n,1,d[x]);
    if(res>=INF)return ;
    for(auto y:vec[x])
        modify(rt[x],1,n,d[y.v],res+y.w);
}
int main()
{
    read(n,m);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u,v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        read(x,y,z);
        vec[x].push_back({y,z});
    }
    d[1]=1,tr[0].val=INF;
    dfs(1,0);
    ll ans=query(rt[1],1,n,1,1);
    printf("%lld\n",(ans>=INF)?-1:ans);
    return 0;
}