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\) 的儿子个数，那么：
最终的答案即把这两条链相加，但其儿子会被计算 \(2\) 次，应该减去。
由于题目是无根树，应该把每个点都当作根比较一次。
#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;
}
T4
不会，用并查集骗了 \(65\) 分