【CF1320E】 Treeland and Viruses 题解
pldzy
·
·
题解
CF 传送门：CF1320E
虚树 + dijkstra。
解法来自 @hs_black。
Solution
1
发现 m 的总和与 n 同级。又因为每次询问只涉及到少数节点，故知道使用虚树去优化。
建虚树优化什么？动态规划似乎不太可做，而病毒感染的过程有些像最短路。
最短路，使用 \text{spfa}？但 \text{spfa} 是无序的，而病毒感染是有序的，也即是说，使用 \text{spfa} 可能会让某些节点挡住病毒过不去，但实际上病毒可以继续感染。
### 2
显然，当前进行的轮数是第一关键字。轮数小的肯定优先被选取。然后在同一轮中，病毒感染的优先级受病毒序号大小的影响。故病毒序号是第二关键字。
那如果两个节点的轮数相同、染上的病毒也相同，我们该优先选择哪个？我们现在在跑最短路，而病毒感染又受两点间路径长度的影响（每个病毒有个参数 $s_i$），故第三关键字是病毒在此轮中还能传染的路径长度。
有了这三个关键字，我们就可以开始跑最短路了。
### 3
讲一些实现的细节。
因为虚树涉及到两点 $\text{LCA}$ 以及每点的时间戳，而且最短路中还要求树上两点间距离，所以使用树链剖分实现。
在建虚树的时候会先扔一个 $1$ 号节点进去，尽管题目中并没说 $1$ 号节点是什么关键节点或者根节点。原因是 $1$ 号节点是我们假定的一个根，从它开始建虚树，这对最终答案并不影响，不过我们在计算完答案初始化的时候能因此简化很多繁琐的特判。
## Code
鄙人不才，写的时候将函数归类了一下，看起来整齐简洁了点，希望能让它方便理解些。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 2e5 + 5;
int n, qst;
int hd[maxn], cnt;
struct edge{int to, nxt;}oe[maxn << 1];
int sz[maxn], mxs[maxn], fa[maxn], dep[maxn];
int tp[maxn], dfn[maxn], tot;
int a[maxn], st[maxn], top;
vector <int> ve[maxn];
int ask[maxn];
struct pnts{
int col, v, di, ti;
bool operator <(const pnts &y) const{ return (ti != y.ti ? (ti < y.ti) : (col != y.col ? (col < y.col) : (di > y.di)));}
}vr[maxn], I;
struct que{
pnts p; int x;
bool operator <(const que &j) const { return j.p < p; }
}; priority_queue <que> q;
//-----------------------------------------------
inline void addo(int u, int v){oe[++cnt] = (edge){v, hd[u]}; hd[u] = cnt;}
inline void dfs1(int u, int f){
fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1;
for(int v, i = hd[u]; i; i = oe[i].nxt){
if((v = oe[i].to) == f) continue;
dfs1(v, u), sz[u] += sz[v];
if(sz[mxs[u]] < sz[v]) mxs[u] = v;
}
}
inline void dfs2(int u, int anc){
tp[u] = anc, dfn[u] = ++tot;
if(!mxs[u]) return; dfs2(mxs[u], anc);
for(int v, i = hd[u]; i; i = oe[i].nxt)
if((v = oe[i].to) ^ fa[u] and v ^ mxs[u]) dfs2(v, v);
}
inline int LCA(int x, int y){
while(tp[x] != tp[y]){
if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
x = fa[tp[x]];
} return dep[x] < dep[y] ? x : y;
}
//----------------Tree_Chain---------------------
inline bool cmp(int x, int y){return dfn[x] < dfn[y];}
inline void addv(int u, int v){ve[u].push_back(v), ve[v].push_back(u);}
inline void insrt(int x){
int lca = LCA(x, st[top]);
if(top == 1 or lca == st[top]){st[++top] = x; return;}
while(top > 1 and dfn[st[top - 1]] >= dfn[lca]) addv(st[top - 1], st[top]), top -= 1;
if(lca ^ st[top]) addv(st[top], lca), st[top] = lca;
st[++top] = x;
}
inline void build(int tm, int k){
rep(i, 1, tm)
scanf("%d", &a[i]), scanf("%d", &vr[a[i]].v),
vr[a[i]].col = i, vr[a[i]].ti = 0, q.push((que){vr[a[i]], a[i]});
rep(i, 1, k) scanf("%d", &ask[i]), a[++tm] = ask[i];
sort(a + 1, a + tm + 1, cmp);
st[top = 1] = a[0] = 1;
rep(i, 1, tm) if(a[i] != a[i - 1]) insrt(a[i]);
while(top > 0) addv(st[top - 1], st[top]), top -= 1;
}
inline void init(int x, int f){
for(auto nxt : ve[x])
if(nxt ^ f) init(nxt, x);
ve[x].clear(), vr[x] = I;
}
//----------------Virtual_Tree-------------------
inline int dis(int x, int y){return dep[x] + dep[y] - 2 * dep[LCA(x, y)];}
inline pnts updt(int lst, int nw){
int d = dis(lst, nw); pnts rec = vr[lst];
if(d <= vr[lst].di){rec.di -= d; return rec;}
d -= vr[lst].di; int dt = (d - 1) / vr[lst].v + 1;
rec.di = dt * vr[lst].v - d, rec.ti += dt;
return rec;
}
inline void dijkstra(){
while(!q.empty()){
que nw = q.top(); q.pop();
if(vr[nw.x] < nw.p) continue;
for(auto nxt : ve[nw.x]){
pnts tmp = updt(nw.x, nxt);
if(tmp < vr[nxt])
vr[nxt] = tmp, q.push((que){vr[nxt], nxt});
}
}
}
//----------------Dijkstra-----------------------
int main(){
scanf("%d", &n);
rep(i, 2, n){
int x, y; scanf("%d%d", &x, &y);
addo(x, y), addo(y, x);
} dfs1(1, 0), dfs2(1, 1);
I.col = I.ti = n + 1; rep(i, 1, n) vr[i] = I;
scanf("%d", &qst);
while(qst--){
int k, m; scanf("%d%d", &m, &k);
build(m, k), dijkstra();
rep(i, 1, k) printf("%d ", vr[ask[i]].col);
printf("\n"), init(1, 0);
}
return 0;
}
```
------------
感谢阅读。