https://ac.nowcoder.com/acm/contest/6173/B
有一天clccle和rqy走在某个国家的街头上,机智的rqy却发现周围的行人不太对劲,他们嘴里念念有词,说着"sqn tql!",一边漫无目的的行走,clccle也发现了这一点,却惊讶的发觉这种奇怪的病毒会向周围的城市,最终会感染整个国家,因为网络已经崩溃,所以她们忘记了自己所在的城市,她们唯一知道的是这种病毒是从当前她们所在的城市开始传播的,并且这个国家的所有城市到这个城市的距离和最小（所有道路的距离都为1）,现在给定聪明的你一张整个国家的地图,请你帮rqy和clccle找到她们现在可能在这个国家的哪一个城市. 输入描述:
两个整数n,m,代表这个国家一共有n个城市,城市之间只有m条道路
接下来m行,每行两个整数a,b代表城市a,b之间有一条联通的道路 输出描述: 多个整数,输出当前clccle和rqy可能所在的点 示例1 输入 复制
2 1 1 2输出 复制
1 2 备注:对于所有的数据,1<=m<=n<=50000
(图的类型保证没有大小大于等于3的环)
这个没有大于等于3的环也就相当于是环， 基本上可以看成数， 题目意思相当于求每个点到其他所有点的最短距离之和，然后再看看哪些点最小 ， 直接换根dp 求 每个点 dp[u] 表示u点到所有其他所有点的最短距离之和
第一次dfs的时候从下向上传递 ， 此时dp[u]表示u点到子树中所有点的最短距离之和 ， x节点对当前节点的贡献是 dp[x] + size[x] , 其含义在孩子节点x的基础上面，所有的子节点全部深度全部加一 ， 也就是 + size[x]从上到下传递的时候，当前节点u对孩子节点的贡献是 dp[u] - dp[x] - size[x] + size[u] - size[x] ，解释： 先将当前节点的dp[u] 剪掉 所要传孩子节点x的dp[x] 贡献删掉， 根据第一步 ， 其贡献是dp[x] + size[x] , size[u] 要减掉size[x] , 这两个dp[u] - dp[x] - size[x] , 和 size[u] - size[x] , 都相当于在下传贡献的时候， 先将孩子节点的贡献删掉 , 然后将孩子节点数量改变一下，因为下一次x节点就变成了根节点 ， dp值要变， size孩子节点也要变， 之后要用到。 #include <iostream> #include <cstdio> #include <algorithm> #include <unordered_map> #include <vector> #include <map> #include <list> #include <queue> #include <cstring> #include <cstdlib> #include <ctime> #include <cmath> #include <stack> #include <set> #pragma GCC optimize(3 , "Ofast" , "inline") using namespace std ; #define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) #define x first #define y second typedef long long ll ; const double esp = 1e-6 , pi = acos(-1) ; typedef pair<int , int> PII ; const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7; ll in() { ll x = 0 , f = 1 ; char ch = getchar() ; while(!isdigit(ch)) {if(ch == '-') f = -1 ; ch = getchar() ;} while(isdigit(ch)) x = x * 10 + ch - 48 , ch = getchar() ; return x * f ; } vector<int> v[N] ; int size[N] , dp[N] , n , m ; void dfs(int u , int f) { size[u] = 1 ; for(auto x : v[u]) { if(x == f) continue ; dfs(x , u) ; size[u] += size[x] ; dp[u] += dp[x] + size[x] ; } return ; } void dfs1(int u , int f , int sum , int res) { dp[u] += sum ; size[u] += res ; for(auto x : v[u]) { if(x == f) continue ; dfs1(x , u , dp[u] - dp[x] - size[x] + size[u] - size[x] , size[u] - size[x]) ; } return ; } int main() { n = in() , m = in() ; for(int i = 1 , a , b ; i <= m ;i ++ ) a = in() , b = in() , v[a].push_back(b) , v[b].push_back(a) ; dfs(1 , 0) ; dfs1(1 , 0 , 0 , 0) ; int ans = INF ; for(int i = 1; i <= n ;i ++ ) ans = min(ans , dp[i]) ; for(int i = 1; i <= n ;i ++ ) if(dp[i] == ans) cout << i << " " ; puts("") ; return 0 ; } /* 9 8 1 2 2 3 3 5 3 6 1 4 4 7 4 8 7 9 */