西安做视频网站公司,志勋网站建设公司,seo黑帽技术,新闻头条最新消息今天发布题目描述
松鼠的新家是一棵树#xff0c;前几天刚刚装修了新家#xff0c;新家有 n n n 个房间#xff0c;并且有 n − 1 n-1 n−1 根树枝连接#xff0c;每个房间都可以相互到达#xff0c;且俩个房间之间的路线都是唯一的。天哪#xff0c;他居然真的住在“树”上。 …题目描述
松鼠的新家是一棵树前几天刚刚装修了新家新家有 n n n 个房间并且有 n − 1 n-1 n−1 根树枝连接每个房间都可以相互到达且俩个房间之间的路线都是唯一的。天哪他居然真的住在“树”上。
松鼠想邀请小熊维尼前来参观并且还指定一份参观指南他希望维尼能够按照他的指南顺序先去 a 1 a_1 a1再去 a 2 a_2 a2……最后到 a n a_n an去参观新家。可是这样会导致重复走很多房间懒惰的维尼不停地推辞。可是松鼠告诉他每走到一个房间他就可以从房间拿一块糖果吃。
维尼是个馋家伙立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间 a n a_n an 是餐厅餐厅里他准备了丰盛的大餐所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入格式
第一行一个正整数 n n n表示房间个数第二行 n n n 个正整数依次描述 a 1 , a 2 , ⋯ , a n a_1, a_2,\cdots,a_n a1,a2,⋯,an。
接下来 n − 1 n-1 n−1 行每行两个正整数 x , y x,y x,y表示标号 x x x 和 y y y 的两个房间之间有树枝相连。
输出格式
一共 n n n 行第 i i i 行输出标号为 i i i 的房间至少需要放多少个糖果才能让维尼有糖果吃。
输入输出样例 #1
输入 #1
5
1 4 5 3 2
1 2
2 4
2 3
4 5输出 #1
1
2
1
2
1说明/提示
对于全部的数据$2 \le n \le 3 \time算法思路
树结构构建
使用邻接表存储树结构add函数。 节点数 n n n访问序列存储在vis数组。 预处理阶段
DFS遍历dfs1函数从根节点设为1出发计算每个节点的深度 d e de de和直接父节点 f a [ i ] [ 0 ] fa[i][0] fa[i][0]。
倍增预处理计算每个节点的 2 j 2^j 2j级祖先用于LCA查询 f a [ i ] [ j ] f a [ f a [ i ] [ j − 1 ] ] [ j − 1 ] ( 1 ≤ j ≤ 20 ) fa[i][j] fa[fa[i][j-1]][j-1] \quad (1 \leq j \leq 20) fa[i][j]fa[fa[i][j−1]][j−1](1≤j≤20)
对数预处理lg数组满足 2 lg [ k ] − 1 ≤ k 2 lg [ k ] 2^{\text{lg}[k]-1} \leq k 2^{\text{lg}[k]} 2lg[k]−1≤k2lg[k]用于LCA跳跃优化。
LCA计算lca函数
调整节点深度若 d e [ a ] d e [ b ] de[a] de[b] de[a]de[b]交换 a , b a,b a,b。 将较深节点上跳到与较浅节点同一深度 a f a [ a ] [ lg [ d e [ a ] − d e [ b ] ] − 1 ] a fa[a][\text{lg}[de[a]-de[b]]-1] afa[a][lg[de[a]−de[b]]−1] 若此时 a b ab ab返回 a a a否则同步上跳至LCA的子节点 a f a [ a ] [ j ] , b f a [ b ] [ j ] ( j 从大到小枚举 ) a fa[a][j], \ b fa[b][j] \quad (j \text{从大到小枚举}) afa[a][j], bfa[b][j](j从大到小枚举)
最终LCA为 f a [ a ] [ 0 ] fa[a][0] fa[a][0]。
路径标记与调整
初始化a[vis[1]] 1。 遍历访问序列 i i i从2到 n n n 对相邻节点对 ( v i s [ i − 1 ] , v i s [ i ] ) (vis[i-1], vis[i]) (vis[i−1],vis[i]) 差分标记b[vis[i-1]], b[vis[i]]。 计算LCA设为 j s js jsb[js]–, b[fa[js][0]]–。 调整a[vis[i-1]]–。 序列结束a[vis[n]]–。 差分数组累加dfs2函数
从叶子向根DFS将子节点的 b b b值累加到父节点 b [ k ] b [ k ] ∑ 子节点 t b [ t ] b[k] b[k] \sum_{\text{子节点}t} b[t] b[k]b[k]子节点t∑b[t]
最终答案
对每个节点 i i i输出 a [ i ] b [ i ] a[i] b[i] a[i]b[i]。 复杂度分析 时间 DFS遍历 O ( n ) O(n) O(n) 倍增预处理 O ( n log n ) O(n \log n) O(nlogn) n − 1 n-1 n−1次LCA查询 O ( n log n ) O(n \log n) O(nlogn) 差分累加 O ( n ) O(n) O(n) 总时间复杂度 O ( n log n ) O(n \log n) O(nlogn) 空间 O ( n log n ) O(n \log n) O(nlogn)存储祖先数组s 10^5$ 1 ≤ a i ≤ n 1 \le a_i \le n 1≤ai≤n。
详细代码
#includebits/stdc.h
using namespace std;
const int N3e55;
int h[N],fa[N][25];
int vis[N],lg[N],de[N];
int a[N],b[N];
int m,n,i,j,x,y,tot;
struct node{int w,to,ne;
}wc[N*2];
void add(int a,int b)
{tot;wc[tot].wa;wc[tot].tob;wc[tot].neh[a];h[a]tot;
}
void dfs1(int k)
{int sh[k];while(s!0){int twc[s].to;if(t!fa[k][0]){fa[t][0]k;de[t]de[k]1;dfs1(t);} swc[s].ne;}
}
int lca(int a,int b)
{if(de[a]de[b]){int ta;ab;bt;}while(de[a]!de[b]){int klg[de[a]-de[b]]-1;afa[a][k];}if(ab) return a;else{for(jlg[de[a]]-1;j0;j--){if(fa[a][j]!fa[b][j]){afa[a][j];bfa[b][j];}}}return fa[a][0];
}
void dfs2(int k)
{int sh[k];while(s!0){int twc[s].to;if(t!fa[k][0]){dfs2(t);b[k]b[t];}swc[s].ne;}
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cinn;for(i1;in;i)cinvis[i]; for(i1;in-1;i){cinxy;add(x,y);add(y,x);}dfs1(1);for(j1;j20;j)for(i1;in;i)fa[i][j]fa[fa[i][j-1]][j-1];for(i1;in;i)lg[i]lg[i-1](1lg[i-1]i?1:0);a[vis[1]];for(i2;in;i){int jslca(vis[i],vis[i-1]);b[vis[i]];b[vis[i-1]];b[js]--;b[fa[js][0]]--;a[vis[i-1]]--;}a[vis[n]]--;dfs2(1);for(i1;in;i)couta[i]b[i]endl;return 0;
}
