做网站设计比较好的公司,2020十大装修公司,刷排名有百度手机刷排名,网站开发前期工作题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid4714 本来想直接求树的直径#xff0c;再得出答案#xff0c;后来发现是错的。 思路#xff1a;任选一个点进行DFS#xff0c;对于一棵以点u为根节点的子树来说#xff0c;如果它的分支数大于1#xff0c…题目链接http://acm.hdu.edu.cn/showproblem.php?pid4714 本来想直接求树的直径再得出答案后来发现是错的。 思路任选一个点进行DFS对于一棵以点u为根节点的子树来说如果它的分支数大于1那么我们把这颗子树从整棵树上剪下来优先减去同时把这颗子树的分支留下两个其它多余的也剪掉然后把剪下来的这些部分连接到根节点那里从而形成一条直链总代价就是我们减的次数把剪下来的部分连接到根节点把最后的直链连成环。在这里剪的次数把剪下来的部分连接到根节点的次数把最后的直链连成环只需要一步。 参考博客https://blog.csdn.net/cc_again/article/details/11407157 代码 #includeiostream
#includecstring
#includealgorithm
#includequeue
#includemap
#includestack
#includecmath
#includevector
#includeset
#includecstdio
#includestring
#includedeque
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 1000005
int n,m,k,t,cnt;
int ans;
struct node{int v,next;
}edge[maxn*2];
int head[maxn];
void add(int u,int v){edge[cnt].vv;edge[cnt].nexthead[u];head[u]cnt;
}
int DFS(int u,int pre){int num0;for(int ihead[u];i!-1;iedge[i].next){int vedge[i].v;if(vpre)continue;numDFS(v,u);}if(num1){//如果以点u为根节点的子树的分支数大于1 if(u1)ansnum-2;elseansnum-1;return 0;//这颗子树剪断了所以返回0 }return 1;//分支数只有一个
}
int main()
{scanf(%d,t);while(t--){scanf(%d,n);int u,v;cnt0;memset(head,-1,sizeof(head));for(int i1;in;i){scanf(%d%d,u,v);add(u,v);add(v,u);}ans0;DFS(1,-1);printf(%d\n,ans*21);}return 0;
} 转载于:https://www.cnblogs.com/6262369sss/p/10034755.html
