Location>code7788 >text

About Virtual Tree

Popularity：626 ℃/2024-09-28 19:40:26

About Virtual Tree

talk irresponsibly

Certain tree issues that give a huge number of nodes when in reality only a small percentage of them can contribute and the rest are just waterboys.To kill all the brain cells of the OIers.

Considering replanting a tree to condense the information and simplify the number of nodes, the resultingimaginary tree。

It probably looks like this:
The red node is the one we chosecrux, i.e., points that can contribute. Both red and black nodes are points in the virtual tree. Black edges are edges in the virtual tree.

Because the LCAs of any two key points are also needed to preserve important information that can maintain the shape of the tree, we need to preserve their LCAs

Apparently, in making sure that dads don't become sons and sons don't become dadsNot even Grandpa. We are free to add the original points to the imaginary tree under the premise of the

You could, of course, add all the points of the original tree to the imaginary tree.It's just that your imaginary tree is as good as built.

Therefore, for convenience, we can first set the\(1\) No. nodes are added to the dummy tree and do not affect the answer

tectonic (geology)

There are two ways of constructing them, where the quadratic ordering method has a larger constant, but is good to remember and understand.

The other, realized with the help of a monotonic stack.

It's up to you.

quadratic ordering

Very intuitive thought process.

The key points are first pressed into\(DFS\) sequential ordering, enumerate each neighboring keypoint, and find it two by two\(LCA\) and add to the sequence\(\mathcal A\) Center.

At this point the sequence\(\mathcal A\) contains all the points in the imaginary tree, but since the keypoints of the\(LCA\) It may be the same, so it still needs to be de-weighted.

So we put the sequence\(\mathcal A\) on the basis of\(DFS\) Order Sort and de-weight from smallest to largest.

Finally, in the sequence\(\mathcal A\) On the enumeration, enumerate the two neighboring points\(x,y\)to find their\(LCA\) hyperlink\(LCA(x,y),y\), will suffice.

Code

int dfn[N];
int a[N],m,A[N],len;//mis the number of key points

bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}

void build(){
	sort(a+1,a+1+m,cmp);
	
	for(int i=1;i<m;i++){
		A[++len]=a[i];
		A[++len]=lca(a[i],a[i+1]);
	}
	A[++len]=a[m];
	
	sort(A+1,A+1+len,cmp);
	len=unique(A+1,A+1+len)-A-1;
	
	for(int i=1;i<len;i++){
		addnew(lca(A[i],A[i+1]),a[i+1]);
	}
}

monotonic stack

The time complexity of solving LCA violently by directly enumerating all keypoint pairs is clearly unacceptable.

We can sort all the keypoints first in DFS order and add them to the tree one by one in that order. At first the tree will only have\(1\) No. Point.

Next, we use a stack to maintain all points in a chain in the tree. All points within this stack satisfy their DFS order monotonically increasing.

Each time you want to set the next keypoint (set to\(u\)) Before entering the stack, find the current top element of the stack and this key point\(u\) LCA\(p\)The points are discussed:

  • If the top of the stack is\(p\)The key points of our accession can then be known\(u\) and points in the stack are on a chain, just add the keypoints to the stack directly. As shown in Figure

  • If the top of the stack is not\(p\)(Apparently this is the time\(p\) (the DFS sequence is larger than the top of the stack, and the subtree at the top of the stack has already been processed).\(p\) is not in the chain, popping the top of the stack until the top of the stack is\(p\), insert key points at this point.
    Remember to connect him to his father's side when you pop the stack.

    left subtree off the stack

Now we've planted our tree!

Code

bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}

int stk[N],top;
void build(){
	sort(a+1,a+1+k,cmp);
	stk[top=1]=1;
	for(int i=1;i<=k;i++){
		if(top==1){
			stk[++top]=a[i];
		}
		int lca=LCA(a[i],stk[top]);
		if(lca==stk[top]) continue;
		while(top>1 && dfn[stk[top-1]]>=dfs[lca]){
			addnew(stk[top-1],stk[top]);
			top--;
		}
		if(lca!=stk[top]){
			addnew(lca,stk[top]);
			stk[top]=lca;
		}
		stk[++top]=a[i];
	}
	while(top>0){//Don't forget to put the concatenated edges in the stack
		addnew(stk[top-1],stk[top]);
		top--;
	}
	return;
}

example

P2495 [SDOI2011] War of attrition

reasoning

Consider resourceful points as key points and build imaginary trees.
For the solar calendar:

For inquiries4 5 7 8 3The imaginary tree constructed

Consider DPing on imaginary trees.

honorific title\(f(u)\) Indicates cut-off\(u\) the cost of all points in the subtree of the\(mn(u)\) denote\(u\) Minimum edge weight on the path to the root node

Two scenarios

in the event that\(u\) There are resources up there, so whatever happens to the subtree.\(u\)are to be separated from the root node, i.e.\(f(u)=mn(u)\)

or else\(min(mn(u),\sum_{v=son[u]}f(v))\)

Code

Here it is implemented with a monotonic stack.

Elaina's Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
#define mkp make_pair
#define psb push_back
#define Elaina 0
#define random(a,b) (1ll*rand()*rand()*rand()%((b)-(a)+1)+(a))
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return f*x;
}
const int mod=998244353;
const int N=1e6+100;
const int inf=0x7fffffff7fffffff;

int n,m,k,a[N];

//sapling
int h[N],idx;
struct EDGE{
	int to,nxt,w;
}e[N];

void add(int x,int y,int z){
	e[++idx]=(EDGE){y,h[x],z};
	h[x]=idx;
}

//imaginary tree
int h1[N],idx1;
struct EDGE1{
	int to,nxt;
}e1[N];

void addnew(int x,int y){
	e1[++idx1]=(EDGE1){y,h1[x]};
	h1[x]=idx1;
}


int cnt,f[N],dfn[N],siz[N],son[N],topf[N],dep[N];
int mn[N];
void dfs1(int x,int fa){
	siz[x]=1;
	f[x]=fa;
	for(int i=h[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa) continue;
		dep[to]=dep[x]+1;
		mn[to]=min(mn[x],e[i].w);
		dfs1(to,x);
		siz[x]+=siz[to];
		if(siz[to]>siz[son[x]]) son[x]=to;
	}
}

void dfs2(int x,int topfa){
	topf[x]=topfa;
	dfn[x]=++cnt;
	if(!son[x]) return ;
	dfs2(son[x],topfa);
	for(int i=h[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!topf[to]){
			dfs2(to,to);
		}
	}
}

int LCA(int x,int y){//arboricultureLCA
	while(topf[x]!=topf[y]){
		if(dep[topf[x]]<dep[topf[y]]) swap(x,y);
		x=f[topf[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	return y;
}

bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}

int stk[N],top;
void build(){//建imaginary tree
	sort(a+1,a+1+k,cmp);
	stk[top=1]=1;
	for(int i=1;i<=k;i++){
		if(top==1){
			stk[++top]=a[i];
		}
		int lca=LCA(a[i],stk[top]);
		if(lca==stk[top]) continue;
		while(top>1 && dfn[stk[top-1]]>=dfn[lca]){
			addnew(stk[top-1],stk[top]);
			top--;
		}
		if(lca!=stk[top]){
			addnew(lca,stk[top]);
			stk[top]=lca;
		}
		stk[++top]=a[i];
	}
	while(top>0){
		addnew(stk[top-1],stk[top]);
		top--;
	}
	return;
}

int dp[N];
int DP(int x){
	if(h1[x]==0) return mn[x];
	int ans=0;
	for(int i=h1[x];i;i=e1[i].nxt){
		int to=e1[i].to;
		ans+=DP(to);
	}
	h1[x]=0;
	return dp[x]=min(ans,1ll*mn[x]);
}

signed main(){
	ios::sync_with_stdio(0),(0),(0);
	
	mn[1]=1ll<<60;
	n=rd;
	for(int i=1;i<n;i++){
		int x=rd,y=rd,z=rd;
		add(x,y,z),add(y,x,z);
	}
	dep[1]=1;
	dfs1(1,0);
	dfs2(1,1);
	m=rd;
	while(m--){
		k=rd;
		for(int i=1;i<=k;i++) a[i]=rd;
		build();
		printf("%lld\n",DP(1));
	}
	
	return Elaina;
}

a reward (bestowed by a superior)

That means it's time to eat, right? Hungry.

<Previous Next>