[bzoj] 3572: [Hnoi2014]世界树

发表于   |   分类于   |  

以前做过两道LCA单调性的题,但是不知道这玩意也叫做虚树哪个混蛋起的第二个名搞的我还以为是是什么高级数据结构呢,弄得我出去听课都听不懂

题意

给定一棵$n$个点的树,有$q$组询问,每一组给定了一些节点,问这些节点每个节点管辖多少个点
定义某个点被管辖当它到这个给定的点距离最小(距离相等取标号最小)

n<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
m[i]为给定节点的标号

传送门

分析

手算一下我们发现节点个数约为$x=\sqrt{2n}$个,极限不到800个点.
显然我们不能在每一次询问做$O(n)$的dp,会T掉.
如果我们能够每一次询问时做$O(x)$的dp,问题就可以解决.

我们还是根据LCA单调性建出虚树,然后对虚树处理.
因为我们要做关于这棵虚树中的点的处理,那么需要预先求得每个节点子树大小.
将虚树中的节点按照dfs序排序,我们就可以两次循环处理出每一条虚树中的每个端点由哪一个节点来控制.
此时我们需要处理每一条边夹在两个端点间的那些节点的控制权
如果一条边的两个端点都由同一个节点来控制,显然中间这些节点都应该被相同的节点控制;
如果两端点由不同节点控制,则需要找到这两个控制点的路径中点在哪里,在中点两侧的节点由两个控制点分别控制.
第二种情况再仔细处理一下路径长度的奇偶性和标号大小即可.

代码

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
#include <cstdio>

#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cstring>

#define  maxn  300010LL
#define  maxm  300010LL
#define  maxk  20LL

struct FST { int to , next ; } re[maxm<<1];
int rstar[maxn] = {0} , rtote = 1 ;
void AddREdge(int u , int v) { re[++rtote].to = v ; re[rtote].next = rstar[u] ; rstar[u] = rtote ; }

int n ;
int Time ;
int q[maxn] , h[maxn] , hh[maxn] ;
int dep[maxn] , dfn[maxn] , size[maxn] ;
int dis[maxn] , ans[maxn] , poi[maxn] , w[maxn] ;
int idx = 0 ;
int fa[maxn][maxk] = {0} ;
int father[maxn] ;

void dfs0(int u , int f) {
truedfn[u] = ++idx , dep[u] = dep[f]+1 , fa[u][0] = f , size[u] = 1 ;
truefor (int p = rstar[u] ; p ; p = re[p].next)
truetrueif (re[p].to != f) dfs0(re[p].to , u) , size[u] += size[re[p].to] ;
}

void ST() {
truefor (int k = 1 , i ; (1<<k) <= n ; k ++ )
truetruefor (i = 1 ; i <= n ; i ++ )
truetruetruefa[i][k] = fa[fa[i][k-1]][k-1] ;
}

int find(int u , int d) {//找到u的深度为d的祖先
trueint i ;
trueRev (i,maxk-1,0)
truetrueif (dep[fa[u][i]] >= d)
truetruetrueu = fa[u][i] ;
truereturn u ;
}

int LCA(int u , int v) {
trueif (!u||!v) return -1 ;
int k ;
trueif (dep[u] < dep[v]) std::swap(u,v) ;
trueRev (k,maxk-1,0)
truetrueif (dep[fa[u][k]] >= dep[v])
truetruetrueu = fa[u][k] ;
trueif (u == v) return u ;
trueRev (k,maxk-1,0)
truetrueif (fa[u][k] != fa[v][k])
truetruetrueu = fa[u][k] ,
truetruetruev = fa[v][k] ;
truereturn fa[u][0] ;
}

bool cmp(const int& a , const int& b) { return dfn[a] < dfn[b] ; }

int sta[maxn] ;
int cnt[maxn] ;
#define  infi  1000000LL

void Solve() {
int i , now , lca , u , v ;
trueread(q[0]) ;
trueh[0] = q[0] ;
truehh[0] = 0 ;
trueRep (i,1,q[0])
truetrueread(q[i]) ,
truetrueans[q[i]] = 0 ,
truetrueh[i] = q[i] ;
truestd::sort(h+1 , h+h[0]+1 , cmp) ;
truesta[sta[0]=1] = 1 ;
trueif (h[1] == 1) i = 2 ;
trueelse i = 1 ;
truefor (;i<=h[0];i++) {
truetruenow = h[i] , lca = LCA(now , sta[sta[0]]) ;
truetrueif (lca == sta[sta[0]]) { sta[++sta[0]] = now ; continue ; }
truetruewhile (sta[0]>1 && lca == LCA(now , sta[sta[0]-1])) {
truetruetruefather[sta[sta[0]]] = sta[sta[0]-1] ;
truetruetruehh[++hh[0]] = sta[sta[0]--] ;
truetruetruedis[hh[hh[0]]] = infi ;
truetruetruelca = LCA(now , sta[sta[0]]) ;
truetrue}
truetrueif (lca != sta[sta[0]]) {
truetruetruefather[sta[sta[0]]] = lca ;
truetruetruehh[++hh[0]] = sta[sta[0]--] ;
truetruetruedis[hh[hh[0]]] = infi ;
truetruetruesta[++sta[0]] = lca ;
truetrue}
truetruesta[++sta[0]] = now ;
true}
truehh[++hh[0]] = sta[sta[0]] ;
truedis[hh[hh[0]]] = infi ;
truewhile ( -- sta[0])
truetruefather[sta[sta[0]+1]] = sta[sta[0]] ,
truetruehh[++hh[0]] = sta[sta[0]] ,
truetruedis[hh[hh[0]]] = infi ;
trueRep (i,1,h[0])
truetruedis[h[i]] = 0 , poi[h[i]] = h[i] ;
truestd::sort(hh+1 , hh+hh[0]+1 , cmp) ;
trueRep (i,1,hh[0]) {
truetruev=hh[i],u=father[v] ;
truetruecnt[v] = size[v] ;
truetrueif (i > 1) w[v] = dep[v]-dep[u] ;
true}
trueRev (i,hh[0],2) {
truetruev=hh[i] , u=father[v] ;
truetrueif (dis[u]>dis[v]+w[v] || (dis[u]==dis[v]+w[v]&&poi[v]<poi[u])) {
truetruetruedis[u] = dis[v]+w[v] ;
truetruetruepoi[u] = poi[v] ;
truetrue}
true}
trueRep (i,2,hh[0]) {
truetruev=hh[i],u=father[v] ;
truetrueif (dis[v]>dis[u]+w[v] || (dis[v]==dis[u]+w[v]&&poi[u]<poi[v])) {
truetruetruedis[v] = dis[u]+w[v] ;
truetruetruepoi[v] = poi[u] ;
truetrue}
true}
int m , sum , mid , tmp ;
trueRep (i,1,hh[0]) {
truetruev=hh[i],u=father[v] ;
truetrueif (i==1) ans[poi[v]] += n-size[v] ;
truetrueelse {
truetruetruem = find(v,dep[u]+1),sum=size[m]-size[v] ;
truetruetrue/*sum为这条两个点间的所有点*/
truetruetruecnt[u] -= size[m] ;
truetruetrue/*下面谈谈分配问题*/
truetruetrueif (poi[u] == poi[v]) ans[poi[v]] += sum ;
truetruetrue/*两端点被同一点控制直接加上*/
truetruetrueelse {
truetruetruetrue/*否则判断中间位置在哪里,然后分配到两个不同的控制点*/
truetruetruetruemid = dep[v]-((dis[u]+dis[v]+w[v])/2-dis[v]) ;
truetruetruetrueif (((dis[u]+dis[v]+w[v])%2==0)&&poi[v]>poi[u])++mid ;
truetruetruetruetmp = size[find(v,mid)]-size[v] ;
truetruetruetrueans[poi[v]] += tmp ;
truetruetruetrueans[poi[u]] += sum-tmp ;
truetruetrue}
truetrue}
true}
trueRep (i,1,hh[0])
truetrueans[poi[hh[i]]] += cnt[hh[i]] ;
trueRep (i,1,q[0])
truetrueprintf("%d ", ans[q[i]]) ;
trueputs("") ;
}

int main() {
int i , u , v ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
trueRep (i,2,n)
truetrueread(u) , read(v) ,
truetrueAddREdge(u,v) ,
truetrueAddREdge(v,u) ;
truedep[0] = 0 ;
truedfs0(1,0) ;
trueST() ;
trueread(Time) ;
truewhile (Time --> 0) Solve() ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章