A.能量树
时间限制: 1000ms 空间限制: 262144kB
题目描述
时间：1s 空间：256M
题目描述：
小信有 n 个节点的有根能量树，根为 1。最开始，树上每个节点的能量都是 0。
现在小信有 n 个能量球，第 i 个能量球拥有 vi 能量。她想把这 n 个能量球分别放置在能量树的每个节点上，使能量树的每个节点都恰好有一个能量球。
小信每次只能放置一个能量球，所以她将进行 n 次操作。每一次操作，她会选择一个能量球，再选择一个没有能量球的能量树节点 x，把刚刚选择的能量球放置在节点 x 上。在这之后，小信能获得以 x 为根的子树中的所有能量球的能量 (包括节点 x 的能量球能量)。
在放置完所有能量球后，小信可能获得的总能量最多是多少？
输入格式：
第一行包含一个整数 n (1≤n≤2⋅10^5)。
第二行包含 n−1 个整数 2,3,…,f2,f3,…,fn (1≤fi≤i−1)，表示节点 i 的父亲是 fi。
第三行包含 n 个整数 1,2,…,v1,v2,…,vn (1≤vi≤10^5)，分别表示能量球的能量。
输出格式：
输出一个整数，表示小信可能获得的最多总能量。
样例输入：
5 1 1 3 3 1 1 2 2 3
样例输出：
22
提示：
样例解释：
能量树如图所示。
第一次操作，小信选择 3 号能量球，它的能量为 2，把它放置在节点 2。在这之后，小信能获得节点 2 中能量球的能量，共 2 能量。
第二次操作，小信选择 4 号能量球，它的能量为 2，把它放置在节点 5。在这之后，小信能获得节点 5 中能量球的能量，共 2 能量。
第三次操作，小信选择 5 号能量球，它的能量为 3，把它放置在节点 4。在这之后，小信能获得节点 4 中能量球的能量，共 3 能量。
第四次操作，小信选择 1 号能量球，它的能量为 1，把它放置在节点 3。在这之后，小信能获得节点 3, 4, 5 中能量球的能量，共 1+2+3=6 能量。
第五次操作，小信选择 2 号能量球，它的能量为 1，把它放置在节点 1。在这之后，小信能获得节点 1, 2, 3, 4, 5 中能量球的能量，共 1+2+1+2+3=9 能量。
所以小信总共获得了 2+2+3+6+9=22 能量。
操作方案不唯一，但可以证明没有操作能获得比 22 更多的总能量，所以答案为 22。
①DFS/BFS 求出每个点到根的距离，排序：大对大（大能量放离根结点远的点）
②求和
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int N=2e5+10;
5 vector<int> q[N];
6 int ar[N],n;
7 int f[N];
8 vector<int> e;
9 bool st[N];
10 int sum;
11 inline void dfs(int x){
12 st[x]=true;
13 for(int i=0;i<q[x].size();i++){
14 int xx=q[x][i];
15 if(!st[xx]){
16 dfs(xx);
17 f[x]+=f[xx];
18 }
19 }
20 sum+=f[x];
21 }
22 inline void bfs(int x){
23 queue<int> p;
24 p.push(x);
25 st[x]=true;
26 while(!p.empty()){
27 int t=p.front();
28 p.pop();
29 e.push_back(t);
30 for(int i=0;i<q[t].size();i++){
31 int xx=q[t][i];
32 if(!st[xx]){
33 st[xx]=true;
34 p.push(xx);
35 }
36 }
37 }
38 }
39 inline void solve(){
40 cin>>n;
41 for(int i=2;i<=n;i++){
42 int a;
43 cin>>a;
44 q[i].push_back(a);
45 q[a].push_back(i);
46 }
47 for(int i=1;i<=n;i++) cin>>ar[i];
48 sort(ar+1,ar+1+n);
49 bfs(1);
50 for(int i=0;i<n;i++) f[e[i]]=ar[i+1];
51 memset(st,0,sizeof st);
52 dfs(1);
53 cout<<sum<<"\n";
54 }
55 signed main(){
56 solve();
57 return 0;
58 }
AC Code
B.旅游路线的数量
时间限制: 2000ms 空间限制: 262144kB
题目描述
时间：2s 空间：256M
题目描述：
一个国家有 n 个城市，城市与城市之间有一些道路，总共有 m 条。
小信在城市 1 ，他想知道从城市 1 出发，有多少条不同的旅游线路，并且要求旅游线路中不能经过同一个城市两次。
可能有很多这样的旅游线路，如果超过 10^6 条，你只需要告诉小信有 10^6 条即可。
输入格式：
第一行包含两个整数 n, m (1≤n≤2⋅10^5, 0≤m≤min(2⋅10^5,n⋅(n−1)/2))。
接下来 m 行，每行两个整数 ui ，vi (1≤ui,vi≤n)，表示城市 u 与 城市 v 之间有一条无向道路。
保证没有重边和自环。
输出格式：
对于每组测试数据，输出一个整数表示答案。
样例1输入：
4 2 1 2 2 3
样例1输出：
3
样例2输入：
4 6 1 2 1 3 1 4 2 3 2 4 3 4
样例2输出：
16
样例3输入：
8 21 2 6 1 3 5 6 3 8 3 6 4 7 4 6 3 4 1 5 2 4 1 2 2 7 1 4 3 5 2 5 2 3 4 5 3 7 6 7 5 7 2 8
样例3输出：
2023
拿样例一举例：
1
1,2
1,3
1,4
1,2,3
1,3,2
1,3,4
1,4,3
1,2,4
1,4,2
1,2,3,4
1,3,2,4
1,4,2,3
1,2,4,3
1,3,4,2
1,4,3,2
共16种
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int N=2e5+10;
5 int n,m;
6 vector<int> q[N];
7 int dist[N];
8 int res=0;
9 bool st[N];
10 inline void dfs(int x){
11 res++;
12 st[x]=true;
13 if(res>=1000000){
14 puts("1000000"); exit(0);
15 }
16 for(int i=0;i<q[x].size();i++){
17 int e=q[x][i];
18 if(!st[e]){
19 dfs(e);
20 }
21 }
22 st[x]=false;
23 }
24 inline void solve(){
25 cin>>n>>m;
26 for(int i=1;i<=m;i++){
27 int a,b;
28 cin>>a>>b;
29 q[a].push_back(b);
30 q[b].push_back(a);
31 }
32 dfs(1);
33 cout<<res<<"\n";
34 }
35 signed main(){
36 solve();
37 return 0;
38 }
AC Code
C.小信跳房子
时间限制: 1000ms 空间限制: 262144kB
题目描述
时间：1s 空间：256M
题目描述：
小信在玩跳房子游戏，已知跳房子游戏的图表现为一颗完美的具有2^(10^100)−1个节点的二叉树。从根节点依次编号为1,2,...,2^(10^100)−1。节点(1≤i≤2^(10^100)−1)的左子节点编号为2i，右子节点编号为2i+1。
小信从从节点x出发，共n步，用一个长度为n的字符串表示小信的移动方向，“U”表示跳到当前所在节点的父节点，“L”表示跳到当前节点的左子节点，“R”表示跳到当前节点的右子节点。
输出小信在跳了n步之后所处的节点编号，保证最终答案不超过10^18。
提示：在跳的过程中节点编号可能超过10^18。
输入格式：
第一行包含两个整数\n,x，表示小信移动次数和初始所在节点编号。
第二行包含一个只含“U”，“L”和“R”的长为n的字符串S。
输出格式：
输出一个整数，表示小信在跳了n步之后所处的节点编号。
样例1输入：
3 2 URL
样例1输出：
6
样例2输入：
6 500000000000000000 RRRUUU
样例2输出：
500000000000000000
约定与提示：
对于100%的数据，1≤n≤10^6;1≤x≤10^18。
样例1：小信的移动路径是2 -> 1 -> 3 -> 6
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int N=1e6+10;
5 int n,x;
6 char ar[N];
7 bool st[N];
8 inline void solve(){
9 cin>>n>>x;
10 for(int i=1;i<=n;i++){
11 cin>>ar[i];
12 }
13 stack<int> q;
14 for(int i=n;i>=1;i--){
15 if(ar[i]=='U') q.push(i);
16 else{
17 if(!q.empty()){
18 st[q.top()]=true;
19 q.pop();
20 st[i]=true;
21 }
22 }
23 }
24 for(int i=1;i<=n;i++){
25 if(!st[i]){
26 if(ar[i]=='U') x/=2;
27 else if(ar[i]=='L') x*=2;
28 else x=x*2+1;
29 }
30 }
31 cout<<x<<"\n";
32 }
33 signed main(){
34 solve();
35 return 0;
36 }
AC Code
D.虫族据点
时间限制: 1000ms 空间限制: 524288kB
题目描述
题目描述
阿斯罗菲克帝国南疆毗邻幽暗森林，其中虫豸横行。
帝宫总管萨拉温格探查发现，虫族似乎已经在森林中建立了 n 个据点，在这些据点之间还有 m 条道路 (双向道路) 供虫族通行。萨拉温格还发现，若 k 个据点之间两两相连，且这 k 个据点与其它任何一个据点都没有道路相连，则这 k 个据点中必然居住了一名虫族大祭司。不论这个 k 是多少，哪怕 k=1，也一定有一名大祭司。
请问总共有几名大祭司。
输入格式
第一行两个整数 n 和 m，接下来 m 行每行两个整数表示一条已经存在的路径。
输出格式
输出一行一个整数，表示大祭司的数量。
样例输入1
6 4 0 1 0 2 1 2 3 4
样例输出1
3
0-1-2，3-4，5 各有一名大祭司。
样例输入2
6 5 0 1 0 2 1 2 3 4 3 5
样例输出2
1
0-1-2 有一名大祭司。
数据规模
1≤n≤100
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=110;
4 vector<int> q[N];
5 int n,m;
6 bool st[N];
7 vector<int> p;
8 int ar[N],br[N];
9 int cr[N];
10 inline void dfs(int x){
11 st[x]=true;
12 p.push_back(x);
13 for(int i=0;i<q[x].size();i++){
14 int e=q[x][i];
15 if(!st[e]){
16 dfs(e);
17 }
18 }
19 }
20 inline void solve(){
21 cin>>n>>m;
22 for(int i=1;i<=m;i++){
23 int a,b;
24 cin>>a>>b;a+=1;b+=1;
25 q[a].push_back(b);
26 q[b].push_back(a);
27 cr[a]++;cr[b]++;
28 }
29 int res=0;
30 for(int i=1;i<=n;i++){
31 if(!st[i]){
32 p.clear();
33 dfs(i);
34 int flag=0;
35 int xx=p.size();
36 for(int j=0;j<xx;j++){
37 if(cr[p[j]]!=xx-1) flag=1;
38 }
39 if(!flag) res++;
40 }
41 }
42 cout<<res;
43 }
44 signed main(){
45 solve();
46 return 0;
47 }
AC Code
标签：10,图论,int,样例,小信,能量,节点 From： https://www.cnblogs.com/ghxx/p/17936781