先学php还是网站建设,seo基础知识,网站分析 案例,临沂招聘信息最新招聘题意#xff1a; 给出一个树#xff0c;把树上任意两个相隔一个点的点加一条边#xff0c;问加完边之后任意两点的距离和是多少. 参考博客 #xff1a;https://blog.csdn.net/Mr_Treeeee/article/details/82960566 思路#xff1a;枚举边的贡献 算出所有点与点之间的距离 给出一个树把树上任意两个相隔一个点的点加一条边问加完边之后任意两点的距离和是多少. 参考博客 https://blog.csdn.net/Mr_Treeeee/article/details/82960566 思路枚举边的贡献 算出所有点与点之间的距离不跳的真实距离。树形DP解决。 可以算每条边被走了几次边(u,v)被走了的次数u的后面前面所有节点数*v的后面前面所有节点数。 实际上就是 一个是u的子树的大小(x)和n-x。 一边和另一边嘛。很容易想通。对于所有边的和就是距离之和ans了。 然后如果都是偶数距离是不是直接除2就行了。但是我们有奇数。 奇数距离是奇数层(深度deep) 和偶数层的点之间的。 所以再记录一下奇数层(y)有几个点就行了。剩下来的都是偶数点。 [ans-y*(n-y)]/2,这个为一直跳着走的距离。减去y*(n-y) 如果这些奇数多出来的1加起来除2答案就多了很多了 然后加回来。 最终答案为[ans-y*(n-y)]/2y*(n-y). #includebits/stdc.h
using namespace std;#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()const int N 2E54;vectorintV[N];
int vis[N];
int num[N],d[N];void dfs(int t,int deep){num[t]1;vis[t]1;for(int i0;iV[t].size();i){if(vis[V[t][i]])continue;vis[V[t][i]]1;d[V[t][i]]deep1;dfs(V[t][i],deep1);num[t]num[V[t][i]];}
}int main(){int n;cinn;int u,v;for(int i1;in;i){scanf(%d %d,u,v);V[u].pb(v);V[v].pb(u);}dfs(1,0);ll ans 0 ;ll c0;for(int i1;in;i){///枚举每条边的贡献///由于跳步的原因 偶数的可以直接除以2 但是下面这个是所有的ansnum[i]*(long long)(n-num[i]);if(d[i]%21) c;}ll k c*(n-c);///减去奇数距离的 /2 然后再加上奇数距离的ans (ans-k)/2k;coutansendl;return 0;
} 转载于:https://www.cnblogs.com/wjhstudy/p/9822234.html
