CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:虚树 [2020/07/30 18:56]
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}$ 数组，需要在建树过程中清零。
@@ 行 610: / 行 610: @@
 </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

用户工具

站点工具

页面工具