2024.04.11 树上问题回顾
P2015 二叉苹果树
树形背包板子题。
需要注意的是，枚举儿子 \(v\) 的选择数量 \(k\) 时，一定要先转移 \(k=0\) 的情况，否则就会用新状态来重复更新新状态，违背 \(0/1\) 背包的思路。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 100 + 5;
int head[maxn],cnt;
struct edge{
int to,nxt,w;
}e[maxn<<1];
inline void link(int u,int v,int w){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].w=w;
}
int n,q,f[maxn][maxn],sz[maxn];
void dfs(int u,int fa){
f[u][0]=0;sz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
sz[u]+=sz[v];
for(int j=min(sz[u]-1,q);j>=0;j--){
for(int k=0;k<=min(sz[v]-1,j);k++){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+e[i].w);
if(k<j)f[u][j]=max(f[u][j],f[u][j-k-1]);
}
}
}
}
int main(){
n=read();q=read();
q=(n-1)-q;
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
link(u,v,w);link(v,u,w);
}
memset(f,0xcf,sizeof f);
dfs(1,0);
cout<<f[1][q]<<endl;
return 0;
}
P4281 [AHOI2008]紧急集合/聚会
树上有三个点 \(x,y,z\)，选择一个点 \(u\) 使得三个点到 \(u\) 的距离和最短。
显然最短路径中，每条树边最多经过一次。
手玩一下发现，\(u\) 一定是三个 \(\text{LCA}\) 中与其余两个不相同的那个。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 5e5 + 10;
const int maxlog = 21;
int head[maxn],cnt=0;
struct edge{
int to,nxt;
}e[maxn<<1];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int f[maxn][21],de[maxn];
void dfs(int u,int fa){
f[u][0]=fa;de[u]=de[fa]+1;
for(int j=1;j<maxlog;j++)f[u][j]=f[f[u][j-1]][j-1];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
}
}
inline int getLCA(int x,int y){
if(de[x]<de[y])swap(x,y);
for(int j=maxlog-1;j>=0;j--)if(de[f[x][j]]>=de[y])x=f[x][j];
if(x==y)return x;
for(int j=maxlog-1;j>=0;j--)if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
return f[x][0];
}
inline int dis(int x,int y){
int LCA=getLCA(x,y);
return de[x]+de[y]-2*de[LCA];
}
int n,m;
int main(){
n=read();m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
link(u,v);link(v,u);
}
dfs(1,0);
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
int L1=getLCA(x,y),L2=getLCA(y,z),L3=getLCA(x,z),LCA;
if(L1==L2)LCA=L3;
else if(L1==L3)LCA=L2;
else LCA=L1;
printf("%d %d\n",LCA,dis(x,LCA)+dis(y,LCA)+dis(z,LCA));
}
return 0;
}
P3629 [APIO2010] 巡逻
有一个 \(n\) 个节点的有根树，根为 \(1\)。要求从根节点 \(1\) 出发，遍历所有的边（进行一次树的遍历），最后回到 \(1\)，每一步的代价是 \(1\)。
现要加入 \(K\in\{1,2\}\) 条非树边，使得满足上述条件的情况下，求代价最小是多少。
如果加入一条非树边，那么形成的环上的树边都从走 \(2\) 次变成了走 \(1\) 次。
贪心的选一定选树的直径，如果 \(K=1\)，那么答案为 \(2(n-1)-L1+1\)，其中 \(L1\) 是直径长度。
如果再连接一条非树边，那么又会形成一个新环。发现如果这个新环和旧环有交叉，那么交叉的所有树边又都会从走 \(1\) 次变回了走 \(2\) 次。
那么在第二次连接非树边时，可以对直径上的边权都从 \(1\) 改为 \(-1\)，这样进行树形 DP 求树的新直径即可，答案为 \(2(n-1)-L1-L2+2\)
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 1e5 + 5;
int head[maxn],cnt=1;
struct edge{
int to,nxt,w;
}e[maxn<<1];
inline void link(int u,int v,int w){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].w=w;
}
int n,K,t1,t2,L1,L2,f[maxn],mp[maxn],Fa[maxn],de[maxn];
void dfs1(int u,int fa){
de[u]=de[fa]+1;
if(de[u]>L1)L1=de[u],t1=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
}
}
void dfs2(int u,int fa){
Fa[u]=fa;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
de[v]=de[u]+1;
mp[v]=i;
if(de[v]>L1)L1=de[v],t2=v;
dfs2(v,u);
}
}
void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
L2=max(L2,f[u]+f[v]+e[i].w);
f[u]=max(f[u],e[i].w+f[v]);
}
}
int main(){
n=read();K=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
link(u,v,1);link(v,u,1);
}
dfs1(1,0);
L1=0;memset(de,0,sizeof de);
dfs2(t1,0);
if(K==1){
cout<<2*(n-1)-(L1-1)<<endl;
return 0;
}
while(t2!=t1){
e[mp[t2]].w=e[mp[t2]^1].w=-1;
t2=Fa[t2];
}
dfs(t1,0);
cout<<2*n-L1-L2<<endl;
return 0;
}