Codeforces 671D Roads in Yusland

设 $f_{u,i}$ 表示覆盖了以 $u$ 为根的子树内的所有边，且向上覆盖到了 $u$ 深度为 $i$ 的祖先的最小代价。
对于 $u$ 和其儿子 $v$，不难合并

$$f_{u,i}^{\prime }=min\left[\underset{j=i}{\overset{n}{min}}(f_{u,i}+f_{v,j}),\underset{j=i}{\overset{n}{min}}(f_{u,j}+f_{v,i})\right]$$

容易线段树合并维护，但是有很多细节（
比如我到现在也不知道为什么不判掉 $u_i=v_i$ 的条件会 WA……

代码：

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 3e5;
int n,m;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
    struct node
    {
        long long val,tag;
        int ls,rs;
    } seg[N * 30 + 5];
    inline void push(int p)
    {
        if(seg[p].tag)
        {
            if(seg[p].ls)
                seg[seg[p].ls].val = min(seg[seg[p].ls].val + seg[p].tag,0x3f3f3f3f3f3f3f3f),
                seg[seg[p].ls].tag = min(seg[seg[p].ls].tag + seg[p].tag,0x3f3f3f3f3f3f3f3f);
            if(seg[p].rs)
                seg[seg[p].rs].val = min(seg[seg[p].rs].val + seg[p].tag,0x3f3f3f3f3f3f3f3f),
                seg[seg[p].rs].tag = min(seg[seg[p].rs].tag + seg[p].tag,0x3f3f3f3f3f3f3f3f);
            seg[p].tag = 0;
        }
    }
    void insert(int x,long long k,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (seg[p = ++tot] = seg[0],1),seg[p].val = min(seg[p].val,k);
        if(tl == tr)
            return ;
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
    }
    void clear(int x,int p,int tl,int tr)
    {
        if(!p)
            return ;
        if(tl == tr)
        {
            seg[p].val = 0x3f3f3f3f3f3f3f3f;
            return ;
        }
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? clear(x,seg[p].ls,tl,mid) : clear(x,seg[p].rs,mid + 1,tr);
        seg[p].val = min(seg[seg[p].ls].val,seg[seg[p].rs].val);
    }
    long long query(int l,int p,int tl,int tr)
    {
        if(!p || l <= tl)
            return seg[p].val;
        push(p);
        int mid = tl + tr >> 1;
        long long ret = 0x3f3f3f3f3f3f3f3f;
        l <= mid && (ret = min(ret,query(l,seg[p].ls,tl,mid)));
        ret = min(ret,query(l,seg[p].rs,mid + 1,tr));
        return ret;
    }
    int merge(int p,int q,long long ptag,long long qtag,int tl,int tr)
    {
        if(!p && !q)
            return 0;
        if(!p)
        {
            seg[q].val = min(seg[q].val + qtag,0x3f3f3f3f3f3f3f3f),
            seg[q].tag = min(seg[q].tag + qtag,0x3f3f3f3f3f3f3f3f);
            return q;
        }
        if(!q)
        {
            seg[p].val = min(seg[p].val + ptag,0x3f3f3f3f3f3f3f3f),
            seg[p].tag = min(seg[p].tag + ptag,0x3f3f3f3f3f3f3f3f);
            return p;
        }
        if(tl == tr)
        {
            ptag = min(ptag,seg[q].val),qtag = min(qtag,seg[p].val);
            seg[p].val = min(min(seg[p].val + ptag,seg[q].val + qtag),0x3f3f3f3f3f3f3f3f);
            return p;
        }
        push(p),push(q);
        int mid = tl + tr >> 1;
        long long prval = seg[seg[p].rs].val;
        long long qrval = seg[seg[q].rs].val;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,min(ptag,qrval),min(qtag,prval),tl,mid);
        seg[p].rs = merge(seg[p].rs,seg[q].rs,ptag,qtag,mid + 1,tr);
        seg[p].val = min(seg[seg[p].ls].val,seg[seg[p].rs].val);
        return p;
    }
}
vector<pair<int,int>> top[N + 5];
int fa[N + 5],dep[N + 5];
int rt[N + 5];
void dfs(int p)
{
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,
            dfs(to[i]),
            SEG::clear(dep[to[i]],rt[to[i]],1,n),
            !rt[p] ? (rt[p] = rt[to[i]]) : (rt[p] = SEG::merge(rt[p],rt[to[i]],0x3f3f3f3f3f3f3f3f,0x3f3f3f3f3f3f3f3f,1,n));
    for(auto u : top[p])
        SEG::insert(dep[u.first],min(u.second + (pre[first[p]] ? SEG::query(dep[u.first],rt[p],1,n) : 0),0x3f3f3f3f3f3f3f3f),rt[p],1,n);
}
int main()
{
    SEG::seg[0].val = 0x3f3f3f3f3f3f3f3f;
    scanf("%d%d",&n,&m);
    if(n == 1)
    {
        puts("0");
        return 0;
    }
    int u,v;
    for(register int i = 2;i <= n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    int c;
    for(;m;--m)
        scanf("%d%d%d",&u,&v,&c),u ^ v && (top[u].push_back(make_pair(v,c)),1);
    dep[1] = 1,dfs(1);
    printf("%lld\n",SEG::seg[rt[1]].val == 0x3f3f3f3f3f3f3f3f ? -1 : SEG::seg[rt[1]].val);
}