1、树的最大独立集
(tree1.cpp)
对于一棵n个节点的无根树,给出n-1条边,选出尽量多的节点,使得任何两个节点均不相邻(称为最大独立集)。输出一个最大独立集的数量。
【输入格式】
第一行一个整数n,表示结点数。接下来n-1行,每行两个整数a,b,表示结点a和b有边。
【输出格式】
一个整数表示最大独立集的数量。
【输入样例】
8
1 2
3 1
7 3
5 4
6 5
8 6
3 4
【输出样例】
4
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 500005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int head[N];
int to[N];
int nex[N];
int tot,n;
int fa[100050][25];
int gs[N];
int s[N];
int d[N];
inline void add(int x,int y){
++tot;
nex[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int u,int fat){
for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=nex[i]){
int dmf=to[i];
if(dmf==fat)continue;
fa[dmf][0]=u;
dfs(dmf,u);
}
d[u]=max(s[u],gs[u]+1);
s[fa[u][0]]+=d[u];
gs[fa[u][1]]+=d[u];
}
int main(){
freopen("tree1.in","r",stdin);
freopen("tree1.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
int x,y;
x=read();
y=read();
add(x,y);
add(y,x);
}
dfs(1,0);
printf("%d",d[1]);
return 0;
}
2、树的重心
(tree2.cpp)
对于一棵n个结点的无根树,找到一个点,使得把树变成以该点为根的有根树时,最大子树的结点数最小。换句话说,删除这个点后最大连通块(一定是树)的结点数最小。
【输入格式】
第一行一个整数n,表示结点数。接下来n-1行,每行两个整数a,b,表示结点a和b有边。
【输出格式】
一行,两个整数,第一整数为删除的结点编号,第二个整数为删除此结点后其最大子树的结点数量。
【输入样例】
11
3 4
1 2
3 1
5 3
5 10
4 7
11 6
4 8
5 9
3 6
【输出样例】
3 3
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 500005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int head[N];
int to[N];
int nex[N];
int son[N];
bool vis[N];
int tot,n;
int size;
int ans;
inline void add(int x,int y){
++tot;
nex[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int cur){
vis[cur]=1;
son[cur]=0;
int tmp=0;
for(int i=head[cur];i;i=nex[i]){
int dmf=to[i];
if(!vis[dmf]){
dfs(dmf);
son[cur]+=son[dmf]+1;
tmp=max(tmp,son[dmf]+1);
}
}
tmp=max(tmp,n-son[cur]-1);
if(tmp<size||tmp==size&&cur<ans){
ans=cur;
size=tmp;
}
}
int main(){
freopen("tree2.in","r",stdin);
freopen("tree2.out","w",stdout);
n=read();
size=2147483640;
for(int i=1;i<n;i++){
int x,y;
x=read();
y=read();
add(x,y);
add(y,x);
}
dfs(1);
printf("%d %d\n",ans,size);
return 0;
}
3、树的最长路径
(tree3.cpp)
对于一棵n个结点的无根树,找到一条最长路径。换句话说,要找到两个点,使得它们的距离最远。
【输入格式】
第一行一个整数n,表示结点数。接下来n-1行,每行两个整数a,b,表示结点a和b有边。
【输出格式】
一行,一个整数,表示最长路径的长度,即边的数量。
【输入样例】
6
1 2
3 1
4 3
5 3
5 6
【输出样例】
4
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define N 200005
using namespace std;
int n,tot;
int nex[N*2];
int to[N*2];
int head[N*2];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool vis[N*2];
int dis[N*2];
inline void add(int x,int y){
++tot;
nex[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
inline int spfa(int u){
queue<int> q;
memset(dis,0x7f7f7f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(u);
dis[u]=0;
vis[u]=1;
while(!q.empty()){
int dmf=q.front();
q.pop();
for(int i=head[dmf];i;i=nex[i]){
if(dis[to[i]]>dis[dmf]+1){
dis[to[i]]=dis[dmf]+1;
if(!vis[to[i]]){
vis[to[i]]=1;
q.push(to[i]);
}
}
}
vis[dmf]=0;
}
int maxn=0;
int id;
for(int i=1;i<=n;i++){
if(i!=u){
if(dis[i]>maxn){
id=i;
maxn=dis[i];
}
}
}
return id;
}
int main(){
freopen("tree3.in","r",stdin);
freopen("tree3.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
int x,y;
x=read();
y=read();
add(x,y);
add(y,x);
}
int ans=0;
int id=spfa(1);
ans+=dis[id];
int ans1=ans;
int id2=spfa(id);
if(id==1) ans=max(ans,dis[id2]);
else ans+=dis[id2];
printf("%d",ans-ans1);
return 0;
}