题意:求树的重心(删除该点后子树最大的最小)
解题关键:想树的结构,删去某个点后只剩下它的子树和原树-此树所形成的数,然后第一次dp求每个子树的节点个数,第二次dp求解答案即可。
此题一开始一直T,后来加了输入挂才过,第一次见卡cin+关同步的题目。
用scanf试了一下,也可以过,0.5s,看来cin关同步和scanf差距也是蛮大的。
任何时候树形dp在dfs中做两次循环都是没必要的。只要了解是先序遍历和后序遍历,在一个for中处理即可。
poj2378将改为n/2即可。
优化:循环的部分少了 最终141ms
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int head[maxn],tot,n;
struct edge{
int to;
int nxt;
int w;
}e[maxn<<]; void add_edge(int u,int v,int w){
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot++;
}
int dp[maxn<<],cnt[maxn]; void dfs(int u,int fa){
cnt[u]=;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
cnt[u]+=cnt[v];
dp[u]=max(dp[u],cnt[v]);
}
dp[u]=max(n-cnt[u],dp[u]);
}
inline int read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
int x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';
if(k=='-')x=-x;return x;
}
int main(){
n=read();
memset(head,-,sizeof head);
tot=;
int a,b;
for(int i=;i<n-;i++){
a=read();
b=read();
add_edge(a,b,);
add_edge(b,a,);
}
dfs(,-);
int ans=inf;
for(int i=;i<=n;i++){
ans=min(ans,dp[i]);
}
bool flag=false;
for(int i=;i<=n;i++){
if(dp[i]==ans){
if(flag) printf(" ");
printf("%d",i);
flag=true;
}
}
printf("\n");
return ;
}
一:219ms
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int head[maxn],tot,n;
struct edge{
int to;
int nxt;
int w;
}e[maxn<<];
void add_edge(int u,int v,int w){
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot++;
}
int dp[maxn<<],cnt[maxn];
void dfs(int u,int fa){
cnt[u]=;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
cnt[u]+=cnt[v];
}
dp[u]=n-cnt[u];
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dp[u]=max(dp[u],cnt[v]);
}
} inline int read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
int x=;for(;ls>=''&&ls<='';ls=getchar())x=x*+ls-'';
if(k=='-')x=-x;return x;
}
int main(){
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
n=read();
memset(head,-,sizeof head);
tot=;
int a,b;
for(int i=;i<n-;i++){
//scanf("%d%d",&a,&b);
//cin>>a>>b;
a=read();
b=read();
add_edge(a,b,);
add_edge(b,a,);
}
dfs(,-);
int ans=inf;
for(int i=;i<=n;i++){
ans=min(ans,dp[i]);
}
bool flag=false;
for(int i=;i<=n;i++){
if(dp[i]==ans){
if(flag) printf(" ");
printf("%d",i);
flag=true;
}
}
printf("\n");
return ;
}
两个dfs分开的形式,练习一下。读入挂将*10变为(x<<3)+(x<<1),变为188ms了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int head[maxn],tot,n;
struct edge{
int to;
int nxt;
int w;
}e[maxn<<]; void add_edge(int u,int v,int w){
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot++;
}
int dp[maxn<<],cnt[maxn]; void dfs(int u,int fa){
cnt[u]=;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
cnt[u]+=cnt[v];
}
} void dfs2(int u,int fa){
dp[u]=n-cnt[u];
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs2(v,u);
dp[u]=max(dp[u],cnt[v]);
}
} inline int read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
int x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';
if(k=='-')x=-x;return x;
}
int main(){
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
n=read();
memset(head,-,sizeof head);
tot=;
int a,b;
for(int i=;i<n-;i++){
//scanf("%d%d",&a,&b);
//cin>>a>>b;
a=read();
b=read();
add_edge(a,b,);
add_edge(b,a,);
}
dfs(,-);
dfs2(,-);
int ans=inf;
for(int i=;i<=n;i++){
ans=min(ans,dp[i]);
}
bool flag=false;
for(int i=;i<=n;i++){
if(dp[i]==ans){
if(flag) printf(" ");
printf("%d",i);
flag=true;
}
}
printf("\n");
return ;
}