电子商务网站建设实训报告心得,外贸公司怎么接订单,有什么做礼品的卖家网站,网站建设行业报告P3174 [HAOI2009]毛毛虫 题目描述 对于一棵树#xff0c;我们可以将某条链和与该链相连的边抽出来#xff0c;看上去就象成一个毛毛虫#xff0c;点数越多#xff0c;毛毛虫就越大。例如下图左边的树#xff08;图 1 #xff09;抽出一部分就变成了右边的一个毛毛虫了我们可以将某条链和与该链相连的边抽出来看上去就象成一个毛毛虫点数越多毛毛虫就越大。例如下图左边的树图 1 抽出一部分就变成了右边的一个毛毛虫了图 2 。 输入输出格式 输入格式 在文本文件 worm.in 中第一行两个整数 N M 分别表示树中结点个数和树的边数。 接下来 M 行每行两个整数 a, b 表示点 a 和点 b 有边连接 a, b ≤ N 。你可以假定没有一对相同的 (a, b) 会出现一次以上。 输出格式 在文本文件 worm.out 中写入一个整数 , 表示最大的毛毛虫的大小。 输入输出样例 输入样例#1 复制 13 12
1 2
1 5
1 6
3 2
4 2
5 7
5 8
7 9
7 10
7 11
8 12
8 13 输出样例#1 复制 11 说明 40% 的数据 N ≤ 50000 100% 的数据 N ≤ 300000 /*
类似dfs求直径
r[]为入度
一条毛毛虫的点数为
Σr[i]-(链长-1)1
Σ(r[i]-1)2
*/
#includeiostream
#includecstdio
#includecstring#define N 300007using namespace std;
int n,m,ans,cnt,S,T;
int head[N],deep[N],pre[N];
int r[N];
struct edge{int u,v,net;
}e[N1];inline int read()
{int x0,f1;char cgetchar();while(c9||c0){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}inline void add(int u,int v)
{e[cnt].vv;e[cnt].nethead[u];head[u]cnt;
}void dfs(int u,int fa,int num)
{if(numans) Su,ansnum; for(int ihead[u];i;ie[i].net){int ve[i].v;if(vfa) continue;dfs(v,u,numr[v]);}
}int main()
{int x,y;nread();mread();memset(r,-1,sizeof r);for(int i1;in;i){xread();yread();add(x,y);add(y,x);r[x];r[y];}dfs(1,0,r[1]);ans0;dfs(S,0,r[S]);printf(%d\n,ans2);return 0;
} /*
把链连带链上的点的儿子算作一条链
f[x]表示以x为根最大链的大小
维护以某个点为根最大链和次大链计算答案
*/
#includeiostream
#includecstdio
#includecstring#define N 300007using namespace std;
int f[N],head[N],son[N];
int n,m,k,ans,maxx;
struct edge
{int to,net;
}e[N1];inline void add(int u,int v)
{e[k].tov;e[k].nethead[u];head[u]k;
}inline int read()
{int x0,f1;char cgetchar();while(c9||c0){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}void dfs(int u,int fa)
{int v,bigx0,lowx0;for(int ihead[u];i;ie[i].net){ve[i].to;if(v!fa){dfs(v,u);if(f[v]lowx)//维护最大链与次大链 {if(f[v]bigx)lowxbigx,bigxf[v];else lowxf[v];}f[u]max(f[u],f[v]son[u]-1);}}ansmax(ans,lowxbigxson[u]-1);//(-1是因为根节点重复加了)
}int main()
{nread();mread();for(int i1;im;i){int u,v;uread();vread();add(u,v);add(v,u);son[u];son[v]; }for(int i1;in;i)f[i]1;dfs(1,0);printf(%d,ans);
} 转载于:https://www.cnblogs.com/L-Memory/p/9766728.html
