0706练习

11jiang08 / 2023-08-21 / 原文

T1

在一颗无根树上选择尽量少的点，使得它们能够占据树上所有边的至少一个端点。

树形DP，设 \(f[i][j]\) 表示节点 \(i\) 是否选择时所有的最小节点，其中 \(j=0\) 表示不选，\(j=1\) 表示选。

\(x\) 的状态转移方程分为两种情况：

\(j=1\) 时：\(x\) 的儿子选不选均可，\(f[x][1]=\displaystyle \sum_{j \in son[x]}\min\{f[j][0],f[j][1]\}\)
\(j=0\) 时：\(x\) 的儿子必须选（如果父子都不选，则这条边无法被覆盖），\(f[x][1]=\displaystyle \sum_{j \in son[x]}f[j][1]\)

由于题目是无根树，我们可以任选一个节点 \(root\) 作为根，则答案为 \(\max\{f[root][1],f[root][0]\}\)。

#include<bits/stdc++.h>
using namespace std;
int n,f[1509][2],root;
vector<int> to[1509];
void dp(int x,int fa){
	f[x][0]=0;  f[x][1]=1;
	for(int i=0;i<to[x].size();i++){
		if(to[x][i]==fa)  continue;
		dp(to[x][i],x);
	}
	for(int i=0;i<to[x].size();i++){
		if(to[x][i]==fa)  continue;
		f[x][1]+=min(f[to[x][i]][1],f[to[x][i]][0]);
		f[x][0]+=f[to[x][i]][1];
	}
	return ;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int id,num,x;
		cin>>id>>num;
		if(i==1)  root=id;
		f[id][1]=f[id][0]=0x3f3f3f3f;
		for(int j=1;j<=num;j++){
			cin>>x;  to[id].push_back(x);
			to[x].push_back(id);
		}
	}
	dp(root,-1);
	cout<<min(f[root][1],f[root][0])<<endl;
	return 0;
}

T2

给定一个无根树，找出一条路径，将路径上的点的数量，加上与这条路径距离为 \(1\)（即 \(1\) 条边）的点的数量，求这个答案的最大值。

概括：求一条路径，使 “路径的点数+不在路径上且与路径有连边的点数” 最大化。

将原问题转化为求两条最长无转折的链满足 “链的点数+不在链上且与链有连边的点数” 最大化。可以用 DP 求解。

设 \(f[i][1]\) 表示以 \(i\) 为根的最长链，\(f[i][2]\) 表示以 \(i\) 为根的次长链，初始化均为 \(1\)。

设 \(max1\) 表示节点 \(x\) 的儿子中的最长链，\(max2\) 表示节点 \(x\) 的所有儿子中的次长链，\(son[x]\) 表示 \(x\) 的儿子个数，那么：

\[f[x][1]=max1+son[x],f[x][2]=max2+son[x] \]

最终的答案即把这两条链相加，但其儿子会被计算 \(2\) 次，应该减去。

\[ans=\displaystyle\max_{x \in V}\{f[x][1]+f[x][2]-son[x]\} \]

由于题目是无根树，应该把每个点都当作根比较一次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,root,f[300009][3];
vector<int> to[300009];
vector<int> node;
void dp(int x,int fa){
	int maxn1=-INF,maxn2=-INF;
	f[x][1]=f[x][2]=1;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(y==fa)  continue;
		dp(y,x);
	}
	if(to[x].size()==1)  return ;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(y==fa)  continue;
		if(f[y][1]>maxn2)  maxn2=f[y][1];
		if(maxn2>maxn1)  swap(maxn1,maxn2);
	}
	f[x][1]=maxn1+to[x].size()-1;
	f[x][2]=maxn2+to[x].size()-1;
	return ;
}
int main(){
	cin>>n>>m;
	if(n==1){
		cout<<1;
		return 0;
	}
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		if(i==1)  root=a;
		node.push_back(a);  node.push_back(b);
		to[a].push_back(b);  to[b].push_back(a);
	}
	dp(root,-1);
	ll ans=0;
	for(int i=0;i<node.size();i++){
		int x=node[i];
		ans=max(ans,(ll)(f[x][1]+f[x][2]-to[x].size()+1));
	}
	cout<<ans<<endl;
	return 0;
}

T3

一颗有 \(N\) 个结点的树，初始所有的点权值为 \(0\)。

给出 \(K\) 条路径，第 \(i\) 条路径从点 \(s_i\) 到 \(t_i\)。每条路径会给途径的所有点（包括端点）的权值加 \(1\)。

请计算所有点中，最大的权值为多少。

树上差分，对于每一条路径，使得 \(val[s_i],val[t_i]\) 各 \(+1\)，而 \(val[lca(s_i,t_i)],val[fa[lca(s_i,t_i)]]\) 各 \(-1\)。

最后遍历整棵树，求差分数组的前缀和，就可以得到最大权值了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50009;
ll n,k,tot,ans,dep[N],fa[N][19],dfn[N],val[N];
vector<int> to[N];
void dfs(int x,int f){
	fa[x][0]=f;  dep[x]=dep[f]+1;
	dfn[++tot]=x;
	for(int i=1;i<=18;i++)  fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(y==f)  continue;
		dfs(y,x);
	}
}
int LCA(int u,int v){
	if(dep[u]>dep[v])  swap(u,v);
	for(int i=18;i>=0;i--){
		if(dep[fa[v][i]]>=dep[u])  v=fa[v][i];
	}
	if(u==v)  return u;
	for(int i=18;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n-1;i++){
		int x,y;  cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
    dfs(1,0);
    for(int i=1;i<=k;i++){
    	int x,y;  cin>>x>>y;
    	int lca_xy=LCA(x,y);
    	val[x]++;  val[y]++;  val[lca_xy]--;
    	val[fa[lca_xy][0]]--;
	}
	for(int i=n;i>=1;i--)  val[fa[dfn[i]][0]]+=val[dfn[i]];
	for(int i=1;i<=n;i++)  ans=max(ans,val[i]);
    cout<<ans;
    return 0;
}