网站备案时间太长,移动终端网站建设,wordpress主题重新激活,广州外贸营销型网站建设vj地址 题目大意#xff1a;找到每一颗子树的重心 思路#xff1a; 树的重心的性质#xff1a; 树的重心如果不唯一#xff0c;则至多有两个#xff0c;且这两个重心相邻 通过连接一条端点分别在两个树的边#xff0c;来将两个树合并成一个#xff0c;那么新的重心肯定…vj地址 题目大意找到每一颗子树的重心 思路 树的重心的性质 树的重心如果不唯一则至多有两个且这两个重心相邻 通过连接一条端点分别在两个树的边来将两个树合并成一个那么新的重心肯定是在原来这两个树的重心的路径上两颗树合并重心的转移 应该不会有人不知道树的重心的定义吧
根据这个每次合并两个树的时候找到新树的重心就在两个重心的路径上该路径一定会经过根节点所以我们转移重心的时候最多转移到根节点就好了。
具体细节代码有注释
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod2520;
const int N2e510;
int n;
int son[N],d[N],vis[N],p[N],dp[N];
vector int g[200010];
vectorint ans[N];
//转移只有满足son[x]son[u]-son[x]的才能够转移xu时就不能够转移了,两棵树转移到最后的时候
//深度更大的那个必然是重心不是重心的会一直走到树根点如果有两个重心那一定是重心的父节点
void up(int u,int x,int y){//转移向上爬while(x!uson[x]son[u]-son[x]){xp[x];}while(y!uson[y]son[u]-son[y]){yp[y];}if(d[x]d[y]) dp[u]x;else dp[u]y;
}
void dfs(int u,int f){//树形dpvis[u]1;dp[u]u;son[u]1;p[u]f;d[u]d[f]1;for(int v:g[u]){if(vf||vis[v]) continue;dfs(v,u);son[u]son[v];up(u,dp[u],dp[v]);//合并两颗树找到重心}
}
int main(){scanf(%d,n);for(int i1;in-1;i){int u,v;scanf(%d%d,u,v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);for(int i1;in;i){if(son[dp[i]]son[i]-son[dp[i]])//判断父节点是不是重心coutmin(dp[i],p[dp[i]]) max(dp[i],p[dp[i]])endl;else coutdp[i]endl;}return 0;
}
