首页 > 代码库 > TC--SRM-703-Div2-1000-TreeDiameters
TC--SRM-703-Div2-1000-TreeDiameters
题目大意 :
定义树的价值为一棵树上距离为树的直径的点对的个数。
给定一颗树,让你求这个树的一个连通子图形成的树的价值最大值是多少。
首先可以想到一棵树的所有最大直径必然要经过同一点,如果有两条直径不相交,那么必然可以找到一条更长的链。
再者,如果确定了相交的这个点,对于所有这点的子树的最大深度必然只有一个与其他不同或都相同。
那么我们只用把所有的点当做直径的交点,把每个子树每个深度有多少点处理出来,然后计算所有相同的情况。
但是有不同的怎么办?枚举直径长度再计算肯定会超时。但是我们可以观察到,如果长度相差超过1,我们可以把交点向深的那棵子树里移动一下,也就是说在计算深子树的根时会计算到,所以我们只用计算其他相同深树只多1的情况。
代码 :
class TreeDiameters { public: #define MAXN 1005 int head[MAXN],cnt; struct Edge{ int to,next; }e[MAXN*2]; inline void insert(int a,int b) { e[++cnt].next=head[a];head[a]=cnt;e[cnt].to=b; e[++cnt].next=head[b];head[b]=cnt;e[cnt].to=a; } int tot[MAXN],dep[MAXN][MAXN],all[MAXN]; void dfs(int s,int v,int fa,int d) { dep[s][d]++; for(int i=head[v];i;i=e[i].next) if(e[i].to!=fa) dfs(s,e[i].to,v,d+1); } int ans,n; void work(int v) { memset(tot,0,sizeof(tot));tot[0]=1; memset(all,0,sizeof(all)); for(int i=head[v];i;i=e[i].next) { memset(dep[e[i].to],0,sizeof(dep[e[i].to])); dfs(e[i].to,e[i].to,v,1); for(int j=1;j<=n;j++) { all[j]+=tot[j]*dep[e[i].to][j]; tot[j]+=dep[e[i].to][j]; ans=max(ans,all[j]); } } for(int i=head[v];i;i=e[i].next) { for(int j=0;j<=n;j++) { ans=max(ans,(tot[j]-dep[e[i].to][j])*dep[e[i].to][j+1]); } } } int getMax(vector<int> p) { n=p.size();ans=0; for(int i=0;i<n;i++) insert(p[i],i+1); for(int i=0;i<=n;i++) work(i); return ans; } };
TC--SRM-703-Div2-1000-TreeDiameters
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。