CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:虚树 [2020/07/27 22:52]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:虚树 [2020/10/08 22:49] (当前版本)
jxm2001
@@ 行 29: / 行 29: @@
 如果 $p$ 恰好为栈顶节点，则直接将新节点入栈。
-否则，将栈顶节点弹出直到栈顶栈顶节点的下一个节点的 $\text{dfs}$ 序不大于 $p$ 的$\text{dfs}$ 序。
+否则，将栈顶节点弹出直到栈顶节点的下一个节点的 $\text{dfs}$ 序不大于 $p$ 的$\text{dfs}$ 序。
 注意到每当栈顶节点被弹出时他在虚树中的位置已经确定，可以直接将他与下一个栈顶节点连一条边。
@@ 行 56: / 行 56: @@
 \begin{equation}v \text{ 是 }u \text{的儿子节点且} v \text{ 是关键节点，}\text{dp}(u)\gets w(u,v)\end{equation}
-接下来建立虚树，并令 $w(u,v)$ 为 $u\to v$ 路径上的最短边。事实上令 $w(u,v)$ 为 $1\to v$ 的最短边不影响最终答案。
+接下来建立虚树，并令 $w(u,v)$ 为 $u\to v$ 路径上的最短边。事实上令 $w(u,v)$ 为根节点 $\to v$ 的最短边不影响最终答案。
 最后暴力 $\text{dp}$ 即可，时间复杂度 $O(\sum_{i=1}^q k_i\log k_i)$。注意每次新建树时不能暴力清零 $\text{head}$ 数组，需要在建树过程中清零。
@@ 行 324: / 行 324: @@
 对于第二类点的贡献。取虚树上两相邻点在原树上的路径，可以根据到哪个关键节点近将路径分成两段。
-每段路径上的节点及其非路径方向的子树对距离该节点近的关键节点做贡献。
+每段路径上的节点及其非路径方向的子树对距离该节点近的关键节点做贡献，路径分界点可通过倍增查找。
 具体实现过程与上述讨论存在少量差异，详细见代码。
@@ 行 462: / 行 462: @@
 </hidden>
+==== 习题三 ====
+[[https://ac.nowcoder.com/acm/contest/5666/B|牛客暑期多校(第一场) B 题]]
+=== 题意 ===
+定义一棵无限节点的树，任意大于 $1$ 的节点 $p$ 与节点 $\frac p{\text{mindiv}(p)}$ 连一条边，其中 $\text{mindiv}(p)$ 代表 $p$ 的最小素因子。
+多次询问，每次给定 $w_1,w_2\cdots w_m$，求 $\min_u\sum_{i=1}^m w_i\text{dis}(u,i!)$。
+=== 题解 ===
+将这棵树视为以 $1$ 为根的有根树，记 $i!(1\le i\le m)$ 为关键节点。
+显然如果 $u$ 为最佳位置，那么 $u$ 的子树中至少要有一个关键节点，否则令 $v=\text{fa}(u)$，则 $\sum_{i=1}^m w_i\text{dis}(v,i!)\lt \sum_{i=1}^m w_i\text{dis}(u,i!)$。
+于是可以将无限大的树转化为叶子节点只能是关键节点的有限大树。
+假设虚树已经建立，考虑换根 $\text{dp}$ 即可得到最佳答案。
+接下来考虑如何建立虚树。
+首先发现根节点到叶子节点的路径代表的素因子是不增的。
+具体的，将一个数分解质因数并将质因子从小到大排列，得到 $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_k^{\alpha_k}$，则根节点到该节点的路径为
+$$\begin{matrix} \underbrace{p_k,p_k\cdots p_k} & \cdots & \underbrace{5,5\cdots 5} & \underbrace{3,3\cdots 3} & \underbrace{2,2\cdots 2}
+\\ \alpha_k & \cdots & \alpha_3 & \alpha_2 & \alpha_1\end{matrix}$$
+由此不难得出，如果每次优先选择代表素因子小的路径遍历，则 $1!,2!,3!\cdots m!$ 的 $\text{dfs}$ 序递增。
+接下来考虑如何求相邻两数的 $\text{LCA}$ 的深度，记 $i$ 的最大素因子为 $p$。
+根据式子 $i!=(i-1)!\ast i$，不难发现根节点到 $(i-1)!$ 的路径与到 $i!$ 的路径在最开始的不包含 $p$ 的部分完全相同。
+而接下来的路径分叉点产生的原因为 $i!$ 比 $(i-1)!$ 拥有更多的 $p$ 因子。据此不难求出 $\text{LCA}$ 的深度，用树状数组维护即可。
+所有 $\text{LCA}$ 的深度可以提前预处理，总时间复杂度 $O(\max(m\log^2 m)+\sum m)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXP=1e5+5;
+int prime[MAXP],mindiv[MAXP],cnt;
+void Prime(){
+	mindiv[1]=1;
+	_for(i,2,MAXP){
+		if(!mindiv[i])prime[cnt++]=i,mindiv[i]=i;
+		for(int j=0;j<cnt&&i*prime[j]<MAXP;j++){
+			mindiv[i*prime[j]]=prime[j];
+			if(i%prime[j]==0) break;
+		}
+	}
+}
+#define lowbit(x) (x)&(-x)
+int c[MAXP];
+void add(int pos){
+	while(pos<MAXP){
+		c[pos]++;
+		pos+=lowbit(pos);
+	}
+}
+int query(int pos){
+	int ans=0;
+	while(pos){
+		ans+=c[pos];
+		pos-=lowbit(pos);
+	}
+	return ans;
+}
+int d[MAXP],lca_d[MAXP];
+void get_dep(){
+	int pos;
+	d[1]=0;
+	_for(i,2,MAXP){
+		d[i]=d[i-1];
+		for(pos=i;pos!=mindiv[pos];pos/=mindiv[pos])d[i]++;d[i]++;
+		lca_d[i]=query(MAXP-1)-query(pos-1);
+		for(pos=i;pos!=1;pos/=mindiv[pos])add(mindiv[pos]);
+	}
+}
+const int MAXN=2e5+5;
+struct Edge{
+	int to,w,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+int Stack[MAXN],node_d[MAXN],top,tot;
+void build(int k){
+	edge_cnt=0;Stack[top=1]=1;head[1]=0;node_d[1]=0;tot=k;
+	_rep(i,2,k){
+		node_d[i]=d[i];
+		if(lca_d[i]!=node_d[Stack[top]]){
+			while(lca_d[i]<node_d[Stack[top-1]])
+			Insert(Stack[top-1],Stack[top],node_d[Stack[top]]-node_d[Stack[top-1]]),top--;
+			if(lca_d[i]!=node_d[Stack[top-1]]){
+				head[++tot]=0,node_d[tot]=lca_d[i];
+				Insert(tot,Stack[top],node_d[Stack[top]]-node_d[tot]);
+				Stack[top]=tot;
+			}
+			else
+			Insert(Stack[top-1],Stack[top],node_d[Stack[top]]-node_d[Stack[top-1]]),top--;
+		}
+		head[i]=0,Stack[++top]=i;
+	}
+	while(top>1)Insert(Stack[top-1],Stack[top],node_d[Stack[top]]-node_d[Stack[top-1]]),top--;
+}
+int n,w[MAXN],s[MAXN];
+LL ans[MAXN],re;
+void dfs(int u){
+	if(u<=n)s[u]=w[u],ans[1]+=w[u]*node_d[u];
+	else s[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs(v);
+		s[u]+=s[v];
+	}
+}
+void dp(int u){
+	re=min(ans[u],re);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(s[1]-s[v]<s[v]){
+			ans[v]=ans[u]+(s[1]-s[v]*2)*edge[i].w;
+			dp(v);
+		}
+	}
+}
+int main()
+{
+	int root=1;
+	Prime();get_dep();
+	while(~scanf("%d",&n)){
+		_rep(i,1,n)
+		w[i]=read_int();
+		build(n);
+		ans[1]=0,re=1e18;
+		dfs(root);
+		dp(root);
+		enter(re);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题四 ====
+[[https://www.luogu.com.cn/problem/P4242|洛谷p4242]]
+=== 题意 ===
+给定一棵树，每个点有一种颜色。定义 $T(u,v)$ 表示点 $u$ 到点 $v$ 路径的颜色段数。接下来 $q$ 个操作。
+  - 将路径 $u\to v$ 的所有结点颜色修改为 $c$
+  - 给定 $m$ 个点 $a_1,a_2\cdots a_m$。对每个 $i$，询问 $\sum_{j=1}^m T(a_i,a_j)$
+=== 题解 ===
+建立虚树，同时定义 $u\to v$ 的权值为 $u\to v$ 的颜色段数减去最开始 $u$ 颜色的一端。
+树剖维护边修改和边询问，注意合并时需要分别维护左路径和右路径。最后点分治统计答案。时间复杂度 $O((\sum m)\log^2 n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+namespace T{
+	struct Edge{
+		int to,next;
+	}edge[MAXN<<1];
+	int head[MAXN],edge_cnt;
+	void Insert(int u,int v){
+		edge[++edge_cnt]=Edge{v,head[u]};
+		head[u]=edge_cnt;
+		edge[++edge_cnt]=Edge{u,head[v]};
+		head[v]=edge_cnt;
+	}
+	struct Node{
+	    int lc,rc,sum;
+	    Node(int lc=0,int rc=0,int sum=0):lc(lc),rc(rc),sum(sum){}
+	    Node operator + (const Node &b){
+	        if(!sum)return b;
+	        if(!b.sum)return *this;
+	        return Node(lc,b.rc,sum+b.sum-(rc==b.lc));
+	    }
+	}s[MAXN<<2];
+	int a[MAXN],lef[MAXN<<2],rig[MAXN<<2],lazy[MAXN<<2];
+	void push_up(int k){s[k]=s[k<<1]+s[k<<1|1];}
+	void build(int k,int L,int R){
+	    lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+	    if(L==R){
+	    	s[k]=Node(a[M],a[M],1);
+	    	return;
+		}
+	    build(k<<1,L,M);
+	    build(k<<1|1,M+1,R);
+	    push_up(k);
+	}
+	void push_tag(int k,int c){
+	    s[k].lc=s[k].rc=c,s[k].sum=1;
+	    lazy[k]=c;
+	}
+	void push_down(int k){
+	    if(lazy[k]){
+	        push_tag(k<<1,lazy[k]);
+	        push_tag(k<<1|1,lazy[k]);
+	        lazy[k]=0;
+	    }
+	}
+	void update(int k,int L,int R,int v){
+	    if(L<=lef[k]&&rig[k]<=R){
+	        push_tag(k,v);
+	        return;
+	    }
+	    push_down(k);
+	    int mid=lef[k]+rig[k]>>1;
+	    if(mid>=L)
+	    update(k<<1,L,R,v);
+	    if(mid<R)
+	    update(k<<1|1,L,R,v);
+	    push_up(k);
+	}
+	Node query(int k,int L,int R){
+	    if(L<=lef[k]&&rig[k]<=R)
+	    return s[k];
+	    push_down(k);
+	    int mid=lef[k]+rig[k]>>1;
+	    if(mid<L)return query(k<<1|1,L,R);
+	    else if(mid>=R)return query(k<<1,L,R);
+	    else
+	    return query(k<<1,L,R)+query(k<<1|1,L,R);
+	}
+	int c[MAXN],d[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t;
+	int h_son[MAXN],mson[MAXN],p[MAXN];
+	void dfs_1(int u,int fa,int depth){
+	    sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	    for(int i=head[u];i;i=edge[i].next){
+	        int v=edge[i].to;
+	        if(v==fa)continue;
+	        dfs_1(v,u,depth+1);
+	        sz[u]+=sz[v];
+	        if(sz[v]>mson[u]){
+	            h_son[u]=v;
+	            mson[u]=sz[v];
+	        }
+	    }
+	}
+	void dfs_2(int u,int top){
+	    dfn[u]=++dfs_t;p[u]=top;a[dfs_t]=c[u];
+	    if(mson[u])
+	    dfs_2(h_son[u],top);
+	    for(int i=head[u];i;i=edge[i].next){
+	        int v=edge[i].to;
+	        if(v==f[u]||v==h_son[u])continue;
+	        dfs_2(v,v);
+	    }
+	}
+	int query_path(int u,int v){
+	    Node ansu,ansv;
+	    while(p[u]!=p[v]){
+	        if(d[p[u]]<d[p[v]])
+	        swap(u,v),swap(ansu,ansv);
+	        ansu=query(1,dfn[p[u]],dfn[u])+ansu;
+	        u=f[p[u]];
+	    }
+	    if(d[u]>d[v])swap(u,v),swap(ansu,ansv);
+	    swap(ansu.lc,ansu.rc);
+	    return (ansu+query(1,dfn[u],dfn[v])+ansv).sum-1;
+	}
+	void update_path(int u,int v,int w){
+	    while(p[u]!=p[v]){
+	        if(d[p[u]]<d[p[v]])
+	        swap(u,v);
+	        update(1,dfn[p[u]],dfn[u],w);
+	        u=f[p[u]];
+	    }
+	    if(d[u]>d[v])
+	    swap(u,v);
+	    update(1,dfn[u],dfn[v],w);
+	}
+	int LCA(int u,int v){
+	    while(p[u]!=p[v]){
+	        if(d[p[u]]<d[p[v]])
+	        swap(u,v);
+	        u=f[p[u]];
+	    }
+	    if(d[u]>d[v])
+	    swap(u,v);
+	    return u;
+	}
+}
+struct Edge{
+	int to,next,w;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,head[u],w};
+	head[u]=edge_cnt;
+	edge[++edge_cnt]=Edge{u,head[v],w};
+	head[v]=edge_cnt;
+}
+struct cmp{
+	bool operator () (const int a,const int b)const{
+		return T::dfn[a]<T::dfn[b];
+	}
+};
+int Stack[MAXN],top,temp[MAXN],node[MAXN];
+void build(int k){
+	edge_cnt=0;
+	sort(node,node+k,cmp());
+	Stack[top=1]=1;head[1]=0;
+	_for(i,0,k){
+		if(node[i]==1)continue;
+		int p=T::LCA(Stack[top],node[i]);
+		if(p!=Stack[top]){
+			while(T::dfn[p]<T::dfn[Stack[top-1]])
+			Insert(Stack[top-1],Stack[top],T::query_path(Stack[top],Stack[top-1])),top--;
+			if(p!=Stack[top-1])
+			head[p]=0,Insert(p,Stack[top],T::query_path(Stack[top],p)),Stack[top]=p;
+			else
+			Insert(Stack[top-1],Stack[top],T::query_path(Stack[top],Stack[top-1])),top--;
+		}
+		head[node[i]]=0,Stack[++top]=node[i];
+	}
+	while(top>1)Insert(Stack[top-1],Stack[top],T::query_path(Stack[top],Stack[top-1])),top--;
+}
+bool is_key[MAXN],vis[MAXN];
+LL ans[MAXN],slen[MAXN],s1;
+int sz[MAXN],mson[MAXN],tot_sz,root,root_sz,s2;
+void find_root(int u,int fa){
+	sz[u]=1;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		find_root(v,u);
+		sz[u]+=sz[v];
+		mson[u]=max(mson[u],sz[v]);
+	}
+	mson[u]=max(mson[u],tot_sz-sz[u]);
+	if(mson[u]<root_sz){
+		root=u;
+		root_sz=mson[u];
+	}
+}
+void dfs_1(int u,int fa,int len){
+	if(is_key[u])
+	sz[u]=1,slen[u]=len;
+	else
+	sz[u]=slen[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs_1(v,u,len+edge[i].w);
+		sz[u]+=sz[v];
+		slen[u]+=slen[v];
+	}
+}
+void dfs_2(int u,int fa,int len){
+	if(is_key[u])ans[u]+=s1+1LL*len*s2;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs_2(v,u,len+edge[i].w);
+	}
+}
+void query(int u){
+	dfs_1(u,0,1);
+	ans[u]+=slen[u];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v])
+		continue;
+		s1=slen[u]-slen[v];
+		s2=sz[u]-sz[v];
+		dfs_2(v,u,edge[i].w);
+	}
+}
+void solve(int u){
+	int cur_sz=tot_sz;
+	vis[u]=true;query(u);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v])
+		continue;
+		tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN;
+		find_root(v,u);
+		solve(root);
+	}
+}
+void dfs_3(int u,int fa){
+	tot_sz++;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_3(v,u);
+	}
+}
+void dfs_4(int u,int fa){
+	ans[u]=0,vis[u]=is_key[u]=false;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_4(v,u);
+	}
+}
+int main()
+{
+	int n=read_int(),q=read_int(),rt=1;
+	_rep(i,1,n)T::c[i]=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		T::Insert(u,v);
+	}
+	T::dfs_1(rt,0,0);T::dfs_2(rt,1);
+	T::build(1,1,n);
+	while(q--){
+		int opt=read_int();
+		if(opt==1){
+			int u=read_int(),v=read_int();
+			T::update_path(u,v,read_int());
+		}
+		else{
+			int k=read_int();
+			_for(i,0,k){
+				temp[i]=node[i]=read_int();
+				is_key[node[i]]=true;
+			}
+			build(k);
+			tot_sz=0;root_sz=MAXN;
+			dfs_3(rt,0);
+			find_root(rt,0);
+			solve(root);
+			_for(i,0,k)
+			space(ans[temp[i]]);
+			putchar('\n');
+			dfs_4(rt,0);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具