「Luogu P2495」[SDOI2011]消耗战

发表于 |
字数统计: 1k | 阅读时长 ≈ 5

给定一棵有$n$个节点的带边权树和$q$组询问，第$i$条边的边权为$w_i$。对于每组询问，给定$m$个关键点$k_i$，你要给出一个边集使得割掉这些边会$1$号节点无法到达任意一个关键点。
为了方便，你只需要求出这个边集所包含的边的最小边权就行了。

$\texttt{Data Range}:2\leq 2\leq 2.5\times 10^5,m\geq 1,\sum k_i\leq 5\times 10^5,w_i\leq 10^5$

前言

生地终于考完了，我是不能阿克的。

链接

Luogu P2495

BZOJ 2286

题解

这道题普通$\texttt{dp}$显然是$O(nm)$的，布星，只有$\texttt{40 pts}$，吸氧后还是只有$\texttt{50 pts}$。

所以说，怎么做呢？

注意到，$\sum k_i\leq 5\times 10^5$，所以，这道题能不能考虑对关键点动(luan)动(gao)手(yi)脚(xia)呢？

没错，是可以的。手玩样例可以发现，有很多点是没有用到的，于是，何不建一棵新的树，使得这棵树只包含所有用到的点呢？

这是可行的。我们想建的树，就叫做虚树。

虚树的建立

首先，第一个问题，虚树上究竟会有哪些点？

很明显，为了要维持原来的树的祖先关系，所有点间两两的$\texttt{lca}$也要算上。

所以说，建树的复杂度是$O(m^2\log n)$的？

非也，非也。把所有的标记点按$\texttt{dfs}$序排序，在相邻两点求$\texttt{lca}$即可。证明略。

于是建树的复杂度变成了$O(m\log n)$。实际操作的话就用单调栈维护一下就好了，$\texttt{dp}$的话，还是原来那么做呀。

时间复杂度$O(\sum k\log \sum k)$

代码

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
160
161
162
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2.5e5+51;
const li inf=0x3f3f3f3f3f3f3f3f;
struct Edge{
    ll to,prev;
    ll dist;
};
Edge ed[MAXN<<1];
ll nc,qcnt,cnt,tot,cur,tp,from,to,dist;
ll last[MAXN],fa[MAXN],depth[MAXN],size[MAXN],heavy[MAXN],top[MAXN];
ll dfn[MAXN],st[MAXN],key[MAXN];
li minn[MAXN];
vector<ll> vtree[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to,ll dist)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    ed[tot].dist=dist;
    last[from]=tot;
}
inline void dfs(ll node,ll f,ll dep)
{  
    fa[node]=f,depth[node]=dep,size[node]=1;
    ll maxn=-1;
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to!=f)
        {
            minn[ed[i].to]=min(minn[node],(li)ed[i].dist);
            dfs(ed[i].to,node,dep+1);
            size[node]+=size[ed[i].to];
            if(size[ed[i].to]>maxn)
            {
                heavy[node]=ed[i].to,maxn=size[ed[i].to];
            }
        }
    }
}
inline void ddfs(ll node,ll link)
{
    top[node]=link,dfn[node]=++cur;
    if(!heavy[node])
    {
        return;
    }
    ddfs(heavy[node],link);
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to!=fa[node]&&ed[i].to!=heavy[node])
        {
            ddfs(ed[i].to,ed[i].to);
        }
    }
}
inline ll LCA(ll x,ll y)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
        {
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return depth[x]<depth[y]?x:y;
}
inline void push(ll node)
{
    if(tp==1)
    {
        st[++tp]=node;
        return;
    }
    ll lca=LCA(node,st[tp]);
    if(lca==st[tp])
    {
        return;
    }
    while(tp>1&&dfn[st[tp-1]]>=dfn[lca])
    {
        vtree[st[tp-1]].push_back(st[tp]),tp--;
    }
    if(st[tp]!=lca)
    {
        vtree[lca].push_back(st[tp]),st[tp]=lca;
    }
    st[++tp]=node;
}
inline bool cmp(ll x,ll y)
{
    return dfn[x]<dfn[y];
}
inline void createVirtualTree()
{
    sort(key,key+cnt,cmp);
    st[tp=1]=1;
    for(register int i=0;i<cnt;i++)
    {
        push(key[i]);
    }
    while(tp>0)
    {
        vtree[st[tp-1]].push_back(st[tp]),tp--;
    }
}
inline li DP(ll node)
{
    li tmp=0;
    if(!vtree[node].size())
    {
    	return minn[node];
    }
    for(register int i=0;i<vtree[node].size();i++)
    {
        tmp+=DP(vtree[node][i]);
    }
    vtree[node].clear();
    return min(minn[node],tmp);
}
int main()
{
    nc=read();
    for(register int i=0;i<nc-1;i++)
    {
    	from=read(),to=read(),dist=read();
    	addEdge(from,to,dist),addEdge(to,from,dist);
    }
    minn[1]=inf,dfs(1,0,1),ddfs(1,1),qcnt=read();
    for(register int i=0;i<qcnt;i++)
    {
        cnt=read();
        for(register int j=0;j<cnt;j++)
        {
            key[j]=read();
        }
        createVirtualTree();
        printf("%lld\n",DP(1));
    }
}