Wuyanru's blog
0%

[USACO23DEC] Cowntact Tracing P

发表于 分类于 ，

开场不到 2h 过了这题，虽然复杂度比正解大点，但是没有关系。

好像是这次铂金组的最难题？但是我不会这次的 T3 啊。

题目链接。

题意

现在有一棵 个点的树，每一个节点上都有一头牛。

这群牛感染了一种病毒，每一天，若一头未被感染的牛与一头已被感染的牛相邻，这头牛下一天就会被感染。

现在告诉你 天以后哪些牛被感染了，求第 天时最少有几头牛被感染，或报告无解。

组询问，所有询问只有时间 不同。

。

。

。

题解

发现 很小，所以我们只需要对于每一组询问单独考虑就好，对于每一组询问，我们这样求解：

首先我们对于每一个点 ，求出 表示所有最终未被感染的牛中，与 最近的距离是多少。

那么我们就知道，只有 的点 初始才有可能是感染的。

所以我们现在的问题是，在所有 的牛中选出尽可能少的点，使他们恰好可以“覆盖”所有最终被感染的点。

发现整个问题不是很好 dp，所以我们考虑贪心。

考虑如下的贪心过程：

  1. 找到当前未被覆盖的点中，深度最大的那个，记作点 ；
  2. 找到一个点 满足 ，并且 可以覆盖 ，再此基础上，我们要求 的深度最小；
  3. 令 为最初感染的节点，覆盖所有 可以覆盖的点，并令 。

考虑这个贪心为什么是正确的。

如图，点 为 。

因为点 的深度最小，所以选择点 可以覆盖尽可能多的 以上的点。

又因为点 是未被覆盖的点中深度最大的，则 子树内其他未被覆盖点都能被覆盖。

所以我们的贪心策略是正确的。

这样我们就得到了一个 的做法，考虑进行优化。

不难发现，在如上过程中，寻找点 是困难的，但是寻找点 是简单的，因为点 是点 的祖先。

对于每一个点 ，我们求出 与 。

首先容易发现 取得最值的 是相同的。

分析可以发现，若存在两个点 满足 是 的祖先，则有 与 。

那么点 只需要满足 即可，又因为 的单调性，我们容易使用二分找出合法的 。

我们需要点 深度最小，由于 的单调性，这个条件也可以转为 最小，进而转化为 深度最小。

通过上面的分析，我们已经可以找出最优的 ，那么我们就可以直接知道对应的 了。

我们离正解就剩下了最后一步，维护这棵树上的点。

我们的操作分为两种：

  • 选定一个点 ，覆盖所有满足 的点 ；
  • 对于一个点 ，查询点 是否已经被覆盖。

考虑询问操作。

显然，对于一个点 ，若有点 覆盖点 ，那么就有两种情况， 在 子树内和 不在子树内。

若 在 子树内，则 ，使用树剖容易维护这种情况。

若 不在子树内，设 ，则有 。

那么对于每一个点 ，使用树剖维护 在子树内且已经被操作。

对于查询操作，我们需要对于所有 的祖先 查询是否有 。

本质为链最值操作，容易使用树剖维护。

对于修改操作，我们需要对于所有 的祖先 更新 。

相当于是一条链对一个等差数列取 ，注意到等差数列公差为定值 ，所以也容易使用树剖维护。

综上所述，我们可以使用树剖维护这两种操作。

最终的过程，就是我们每一次找当前最深的点，查询它有没有被覆盖。

如果没有被覆盖，就找到上述的 并进行覆盖操作，直至所有点被覆盖。

时间复杂度 。由于树剖常数小，可以通过。

更好的解决方案：

  1. 对于树上的每一条重链，我们单独开一棵动态开点线段树，可以令树剖常数变小；

  2. 由于瓶颈主要在于 不在 子树内的情况，而这一部分只有链操作，所以可以使用全局平衡二叉树换掉树剖，时间复杂度 。

    可能是因为我写的屎，所以这种方案应该是没有第 种跑的快。

  3. 和第三条一样，由于只有链操作，所以将树剖改为点分树，复杂度也为 。

    我是猪，一开始没有想到

代码

由于题解是后来写的，补充了很多细节，所以这份代码和上面讲的有一些细节不同。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
template<const int N,const int M>
struct graph
{
    int head[N+5];
    int t[M+5];
    int x[M+5];
    int cntm;
    graph(){ cntm=1;}
    inline void clear(int n=N)
    {
        cntm=1;
        for(int i=1;i<=n;i++) head[i]=0;
    }
    inline void ad(int u,int v)
    {
        cntm++;
        t[cntm]=v;
        x[cntm]=head[u];
        head[u]=cntm;
    }
    inline void add(int u,int v)
    {
        ad(u,v);
        ad(v,u);
    }
    inline int st(int num){ return head[num];}
    inline int to(int num){ return t[num];}
    inline int nx(int num){ return x[num];}
};
graph<100000,200000>g;
int num[400005];
int ma[400005];
int hson[100005];
int top[100005];
int siz[100005];
int dfn[100005];
int id[100005];
int rk[100005];
int fa[100005][21];
int mad[100005];
bool can[100005];
int dep[100005];
int dis[100005];
char s[100005];
bool v;
int tim;
int n,m;
void dfs(int num)
{
    siz[num]=1;
    for(int i=0;fa[num][i];i++) fa[num][i+1]=fa[fa[num][i]][i];
    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(p==fa[num][0]) continue;
        fa[p][0]=num,dep[p]=dep[num]+1;
        dfs(p),siz[num]+=siz[p];
        if(siz[p]>siz[hson[num]]) hson[num]=p;
    }
}
void dfs(int num,int t)
{
    top[num]=t;dfn[num]=++tim,rk[tim]=num;
    if(hson[num]) dfs(hson[num],t);
    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(p==hson[num]||p==fa[num][0]) continue;
        dfs(p,p);
    }
}
inline void bfs()
{
    memset(dis,0x3f,sizeof(dis));queue<int>que;
    for(int i=1;i<=n;i++) if(s[i]=='0') dis[i]=0,que.push(i);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=g.st(u);i;i=g.nx(i))
        {
            int p=g.to(i);
            if(dis[u]+1<dis[p]) dis[p]=dis[u]+1,que.push(p);
        }
    }
}
inline void init_bfs(int d)
{
    memset(mad,-0x3f,sizeof(mad));queue<int>que;
    for(int i=1;i<=n;i++) if(can[i]) mad[i]=d,que.push(i);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=g.st(u);i;i=g.nx(i))
        {
            int p=g.to(i);
            if(mad[u]-1>mad[p])
            {
                mad[p]=mad[u]-1;
                que.push(p);
            }
        }
    }
}
void change(int p,int pl,int pr,int l,int r,int y)
{
    if(l<=pl&&pr<=r)
    {
        num[p]=max(num[p],y);
        ma[p]=max(ma[p],2*pr+y);
        return ;
    }
    int mid=(pl+pr)>>1;
    if(l<=mid) change(p*2,pl,mid,l,r,y);
    if(mid<r) change(p*2|1,mid+1,pr,l,r,y);
    ma[p]=max(ma[p],max(ma[p*2],ma[p*2|1]));
}
inline int get(int p,int pl,int pr,int l,int r)
{
    int ans=2*min(r,pr)+num[p];
    if(l<=pl&&pr<=r)
    {
        return ma[p];
    }
    int mid=(pl+pr)>>1;
    if(l<=mid) ans=max(ans,get(p*2,pl,mid,l,r));
    if(mid<r) ans=max(ans,get(p*2|1,mid+1,pr,l,r));
    return ans;
}
inline int jump(int u)
{
    int mem=u;
    for(int i=20;i>=0;i--) if(fa[u][i])
    {
        int p=fa[u][i];
        if(dep[p]+mad[p]>=dep[mem]) u=p;
    }
    return u;
}
inline int getd(int p)
{
    int ans=-0x3f3f3f3f;
    while(p)
    {
        // printf("%d %d : %d\n",dfn[top[p]],dfn[p],get(1,1,n,dfn[top[p]],dfn[p]));
        ans=max(ans,get(1,1,n,dfn[top[p]],dfn[p]));
        p=fa[top[p]][0];
    }
    return ans;
}
inline void c(int p)
{
    int now=p;
    while(now)
    {
        int b=mad[p]-dep[p]+2*dep[now]-2*dfn[now];
        change(1,1,n,dfn[top[now]],dfn[now],b);
        // printf("change %d %d %d\n",dfn[top[now]],dfn[now],b);
        now=fa[top[now]][0];
    }
}
inline void output(int p,int pl,int pr)
{
    printf("output %d %d %d : %d %d\n",p,pl,pr,num[p],ma[p]);
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    output(p*2,pl,mid);
    output(p*2|1,mid+1,pr);
}
inline int get(int d)
{
    int ans=0,tot=0;
    memset(num,-0x3f,sizeof(num)),memset(ma,-0x3f,sizeof(ma));
    for(int i=1;i<=n;i++) if(!v||dis[i]>d) can[i]=1;else can[i]=0;
    init_bfs(d);
    for(int i=1;i<=n;i++) if(s[i]=='1')
    {
        id[++tot]=i;
        if(mad[i]<0) return -1;
    }
    sort(id+1,id+tot+1,[](int x,int y){ return dep[x]>dep[y];});
    
    for(int i=1;i<=tot;i++)
    {
        int p=id[i];
        if(getd(p)>=dep[p]) continue;
        int q=jump(p);
        ans++;
        // printf("p=%d q=%d\n",p,q);
        c(q);
        // output(1,1,n);
    }
    return ans;
}
int main()
{
    n=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) if(s[i]=='0') v=1;
    for(int i=1;i<n;i++) g.add(read(),read());
    m=read();dfs(1),dfs(1,1),bfs();
    for(int i=1;i<=m;i++) printf("%d\n",get(read()));
    return 0;
}
/*
5
11111
1 2
2 3
3 4
4 5
1
0
*/

感谢观看！