• Codeforces Round 909 (Div. 3)（A~G）（启发式合并）

    1899A - Game with Integers 

            题意：给定一个数 x , 两个人玩游戏，每人能够执行 +1 / -1操作，若操作完x是3的倍数则获胜，问先手的人能否获胜（若无限循环则先手的人输）。

            思路：假如一个数模3余1或者2，那么第一轮操作先手就能获胜，若余0则后手获胜。

            

    1. // Problem: A. Game with Integers
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/A
    4. // Memory Limit: 256 MB
    5. // Time Limit: 1000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=1e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. int a[N];
    31. void init(int n){
    32. 	for(int i = 0 ; i <= n ; i ++){
    33. 		a[i] = 0;
    34. 	}
    35. }
    36. void solve() 
    37. {
    38. 	cin >> n;
    39. 	if(n % 3 == 0){
    40. 		cout << "Second\n";
    41. 	}	
    42. 	else{
    43. 		cout << "First\n";
    44. 	}	
    45. }            
    46. int main() 
    47. {
    48.     ios::sync_with_stdio(false);
    49.     cin.tie(0);
    50.     cout.tie(0);
    51.     cout.precision(10);
    52.     int t=1;
    53. 	cin>>t;
    54.     while(t--)
    55.     {
    56.     	solve();
    57.     }
    58.     return 0;
    59. }

    1899B - 250 Thousand Tons of TNT  

            题意：给定一个整数n , 表示有 n 个集装箱，接下来给定一个数组a , 代表了第i个集装箱有a_{i}吨重。现要将n个集装箱恰好分成连续的k组。要求这当中所有k的取值下集装箱重量的最大值减去最小值的最大值。

            思路：直接暴力做 ， 假设每一组有1、2、3、4、...n个，看满足题意的情况下最大值减最小值的值。时间复杂度O(NlogN).

            

    1. // Problem: B. 250 Thousand Tons of TNT
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/B
    4. // Memory Limit: 256 MB
    5. // Time Limit: 2000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=2e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. LL a[N] , sum[N];
    31. void init(int n){
    32. 	for(int i = 0 ; i <= n ; i ++){
    33. 		a[i] = 0;
    34. 	}
    35. }
    36. void solve() 
    37. {
    38. 	cin >> n;
    39. 	for(int i = 1 ; i <= n ; i ++){
    40. 		cin >> a[i];
    41. 		sum[i] = sum[i - 1] + a[i];	
    42. 	}
    43. 	LL ans = 0;
    44. 	for(int i = 1 ; i <= n ; i ++){
    45. 		LL maxx = 0 , minn = 1e18;
    46. 		if(n % i == 0){
    47. 			for(int j = 0 ; j < n ; j += i){
    48. 				maxx = max(sum[j + i] - sum[j] , maxx);
    49. 				minn = min(minn , sum[j + i] - sum[j]);
    50. 			}
    51. 			ans = max(ans , maxx - minn);
    52. 		}
    53. 	}
    54. 	cout << ans<
    55. }            
    56. int main() 
    57. {
    58.     ios::sync_with_stdio(false);
    59.     cin.tie(0);
    60.     cout.tie(0);
    61.     cout.precision(10);
    62.     int t=1;
    63. 	cin>>t;
    64.     while(t--)
    65.     {
    66.     	solve();
    67.     }
    68.     return 0;
    69. }

    1899C - Yarik and Array  

            题意：给定一组序列，求连续奇数偶数非空子序列的和的最大值（相邻的奇偶性不能相同）。

            思路：同最大连续子序列差不多的做法，只不过要求前一项和当前的奇偶性不同，且至少要选一项。时间O（N）。

            

    1. // Problem: C. Yarik and Array
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/C
    4. // Memory Limit: 256 MB
    5. // Time Limit: 1000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=2e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. LL a[N];
    31. int dp[N][2];
    32. void init(int n){
    33. 	for(int i = 0 ; i <= n ; i ++){
    34. 		a[i] = 0;
    35. 	}
    36. }
    37. void solve() 
    38. {
    39. 	int n;
    40. 	cin >> n;
    41. 	for(int i = 1 ; i <= n ; i ++)
    42. 		cin >> a[i];
    43. 	LL ans = -1e18;
    44. 	LL now = 0;
    45. 	for(int i = 1 ; i <= n ; i ++){
    46. 		if(now == 0){
    47. 			now += a[i];
    48. 		}
    49. 		else{
    50. 			if(abs(a[i]) % 2 == abs(a[i - 1]) % 2 ){
    51. 				now = a[i];
    52. 			}
    53. 			else{
    54. 				if(now > 0)
    55. 					now += a[i];
    56. 				else
    57. 					now = a[i];
    58. 			}
    59. 		}
    60. 		ans = max(ans , now);
    61. 	//	cout << now << endl;
    62. 		if(now < 0)
    63. 		 	now = 0;
    64. 	}
    65. 	cout << ans << endl;
    66. }            
    67. int main() 
    68. {
    69.     ios::sync_with_stdio(false);
    70.     cin.tie(0);
    71.     cout.tie(0);
    72.     cout.precision(10);
    73.     int t=1;
    74. 	cin>>t;
    75.     while(t--)
    76.     {
    77.     	solve();
    78.     }
    79.     return 0;
    80. }

    1899D - Yarik and Musical Notes 

            题意：给定一组数，要求数对(i , j)满足(2^{a_i})^{2^{a_{j}}} = (2^{a_j})^{2^{a_{i}}}(i < j)的数量。

            思路：构造辅助哈希nex（范围过大无法构造数组） , nex[i]标记了当前位置之后有多少个数字i。观察后发现 ， 当 i = 1 ,j = 2/i = 2 , j = 1时能够满足，其余均需要i=j" role="presentation" style="position: relative;">i=j才能满足。因此对于1或者2而言，数对的数量为nex[1] +nex[2] ，其余的 i 构成的数对数量都是nex[i]。首先遍历一遍算出nex，然后再遍历一遍求答案，同时不断更新nex即可。

            

    1. // Problem: D. Yarik and Musical Notes
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/D
    4. // Memory Limit: 256 MB
    5. // Time Limit: 1000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=3e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. int a[N];
    31. void init(int n){
    32. 	for(int i = 0 ; i <= n ; i ++){
    33. 		a[i] = 0;
    34. 	}
    35. }
    36. void solve() 
    37. {
    38. 	cin >> n;
    39. 	unordered_mapmp;
    40. 	LL ans = 0;
    41. 	for(int i = 1 ; i <= n ; i ++){
    42. 		cin >> a[i];
    43. 		mp[a[i]]++;
    44. 	}
    45. 	for(int i = 1 ; i <= n ; i ++){
    46. 		mp[a[i]]--;
    47. 		if(a[i] == 1 || a[i] == 2){
    48. 			ans += mp[1] + mp[2];
    49. 		}
    50. 		else{
    51. 			ans += mp[a[i]];
    52. 		}
    53. 	}
    54. 	cout << ans << endl;
    55. }            
    56. int main() 
    57. {
    58.     ios::sync_with_stdio(false);
    59.     cin.tie(0);
    60.     cout.tie(0);
    61.     cout.precision(10);
    62.     int t=1;
    63. 	cin>>t;
    64.     while(t--)
    65.     {
    66.     	solve();
    67.     }
    68.     return 0;
    69. }

    1899E - Queue Sort  

            题意：给定一个数组，每次能够进行如下操作：

    1、选择第一个数放入数组最后一个。

    2、将最后一个数往前交换，直到到达第一位或者比前一个数大为止。

            问将数组变为递增的最少操作数，若无法则输出-1.

            思路：若最小的数为数组第一个，那么一轮操作之后他还是在第一位，这样便会无限循环。因此只需要满足最小的数之后的数全是递增的即可。

            

    1. // Problem: E. Queue Sort
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/E
    4. // Memory Limit: 256 MB
    5. // Time Limit: 1000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=3e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. LL a[N];
    31. void init(int n){
    32. 	for(int i = 0 ; i <= n ; i ++){
    33. 		a[i] = 0;
    34. 	}
    35. }
    36. void solve() 
    37. {
    38. 	cin >> n;
    39. 	LL minn = 1e18;
    40. 	for(int i = 1 ;i <= n ; i ++){
    41. 		cin >> a[i];
    42. 		minn = min(a[i] , minn);
    43. 	}
    44. /*	for(int i = 1 ; i < n - 1; i++){
    45. 		if(a[i] < a[i + 1]){
    46. 			break;
    47. 		}
    48. 		if(i == n - 2){
    49. 			cout << 0 << endl;
    50. 			return;
    51. 		}
    52. 	}*/
    53. 	for(int i = 1 ; i <= n ; i ++){
    54. 		if(a[i] == minn){
    55. 			for(int j = i + 1; j <= n ; j ++){
    56. 				if(a[j] < a[j - 1]){
    57. 					cout << -1 << endl;
    58. 					return;
    59. 				}
    60. 			}
    61. 			cout << i - 1 << endl;
    62. 			return;
    63. 		}
    64. 	}
    65. }            
    66. int main() 
    67. {
    68.     ios::sync_with_stdio(false);
    69.     cin.tie(0);
    70.     cout.tie(0);
    71.     cout.precision(10);
    72.     int t=1;
    73. 	cin>>t;
    74.     while(t--)
    75.     {
    76.     	solve();
    77.     }
    78.     return 0;
    79. }

    1899F - Alex's whims  

            题意：现有n个顶点，起初你可以任意构造将其形成一棵树。接下来有 d 个数，表示共有d轮。每一轮你可以选择一个已有的边将其删除，然后再连一条边形成一颗新的数。要求每一轮能够满足至少有两个叶子结点的距离恰好为d_{i}。

            思路：首先可以将n个顶点连城一条链。然后每一轮当中，我们固定第一个点和最后一个点的距离为我们要的d_{i}。每次我们可以将与点1相连的边删去，然后新增一条边，使得刚好1到n的距离为d_{i}。由于结点2 ~ n都是一条链，所以2 ~ n - 1 任意一个距离都是可以构造出来的。如此便一定能够满足题意。所以我们只需要记录当前1结点和哪个结点相连，然后需要连到哪个结点即可。

            

    1. // Problem: F. Alex's whims
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/F
    4. // Memory Limit: 256 MB
    5. // Time Limit: 1000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=1e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25.  
    26. LL lcm(LL a , LL b){
    27. 	return a / gcd(a , b) * b;
    28. }
    29. int n , m;
    30. int a[N];
    31. void init(int n){
    32. 	for(int i = 0 ; i <= n ; i ++){
    33. 		a[i] = 0;
    34. 	}
    35. }
    36. void solve() 
    37. {
    38. 	cin >> n >> m;
    39. 	for(int i = 2 ; i <= n ; i ++){
    40. 		cout << i - 1 << " " << i << endl;
    41. 	}
    42. 	int pre = 2;
    43. 	for(int i = 0 ; i < m ; i ++){
    44. 		int x;
    45. 		cin >> x;
    46. 		int len = (n - pre) + 1;
    47. 		if(len == x){
    48. 			cout <<"-1 -1 -1\n";
    49. 			continue;
    50. 		}
    51. 		else{
    52. 			int to = (n - x + 1);
    53. 			cout << 1 << " " << pre << " " << to << endl;
    54. 			pre = to; 
    55. 		}
    56. 	}
    57. }            
    58. int main() 
    59. {
    60.     ios::sync_with_stdio(false);
    61.     cin.tie(0);
    62.     cout.tie(0);
    63.     cout.precision(10);
    64.     int t=1;
    65. 	cin>>t;
    66.     while(t--)
    67.     {
    68.     	solve();
    69.     }
    70.     return 0;
    71. }

    1899G - Unusual 进入tainment  

            思路：给定一棵树和一个排列p。现有q组询问，每组询问包含了三个数l , r , x。问点x的子树的结点是否在[p_{l} , p_{r}]中出现。

            思路：子树问题，首先想到了用dfs序来解决。对于一颗子树而言，我们可以用set来维护其所有结点在排列p中的位置。然后对于一个询问而言，只需要找到set中大于等于 l 的第一个位置即可，然后判断该位置是否小于等于r。若小于等于r则代表了其子树的结点包含在了[p_{l} , p_{r}]中。共有n个结点，所以我们需要创立n个set，来记录他们的结点在p中的位置。在子树向上合并的过程中，我们可以用启发式合并来实现优化：每一轮虽然是将子树的set合并到父节点的set上，但是可以用swap来交换两个set，确保每次都将小集合合并到大集合上面（swap是O(1)的）。如此总的时间复杂度是O(nlogn + qlogn）的。

            

    1. // Problem: G. Unusual Entertainment
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/G
    4. // Memory Limit: 256 MB
    5. // Time Limit: 3000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=2e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25. LL lcm(LL a , LL b){
    26. 	return a / gcd(a , b) * b;
    27. }
    28. int n , m;
    29. int a[N] , pos[N];
    30. vector<int>tr[N + 5];
    31. vectorint , 3 > >que[N];
    32. vectorint>> num(N);
    33. void init(int n){
    34. 	for(int i = 0 ; i <= n ; i ++){
    35. 		a[i] = 0 , tr[i].clear() , que[i].clear();
    36. 		num[i].clear();
    37. 	}
    38. }
    39. LL ans[N];
    40. void merge(set<int> &a , set<int>&b){
    41. 	if(a.size() < b.size()){
    42. 		swap(a , b);
    43. 	}
    44. 	for(auto it : b){
    45. 		a.insert(it);
    46. 	}
    47. 	b.clear();
    48. }
    49. void dfs(int cur , int f){
    50. 	num[cur].insert(pos[cur]);
    51. 	for(auto it : tr[cur]){
    52. 		if(it == f)
    53. 			continue;
    54. 		dfs(it , cur);
    55. 		merge(num[cur] , num[it]);
    56. 	}
    57. 	for(auto it : que[cur]){
    58. 		auto p = num[cur].lower_bound(it[0]);
    59. 		ans[it[2]] = p != num[cur].end() && *p <= it[1];
    60. 	}
    61. };
    62. void solve() 
    63. {
    64.  
    65. 	cin >> n >> m;
    66. 	for(int i = 1 ; i < n ; i++){
    67. 		int x , y;
    68. 		cin >> x >> y;
    69. 		tr[x].pb(y);
    70. 		tr[y].pb(x);
    71. 	}
    72. 	for(int i = 1 ; i <= n ; i ++){
    73. 		cin >> a[i];
    74. 		pos[a[i]] = i;
    75. 	}
    76. 	for(int i = 0 ; i < m ; i ++){
    77. 		int l , r , x;
    78. 		cin >> l >> r >> x;
    79. 		que[x].pb({l , r , i});
    80. 	}
    81. 	dfs(1 , 0);
    82. 	for(int i = 0 ; i < m ; i ++){
    83. 		if(ans[i]){
    84. 			cout <<"YES\n";
    85. 		}
    86. 		else{
    87. 			cout <<"NO\n";
    88. 		}
    89. 	}
    90. 	init(n);
    91. 	cout << endl;
    92. 	num.clear();
    93. }            
    94. int main() 
    95. {
    96.     ios::sync_with_stdio(false);
    97.     cin.tie(0);
    98.     cout.tie(0);
    99.     cout.precision(10);
    100.     int t=1;
    101. 	cin>>t;
    102.     while(t--)
    103.     {
    104.     	solve();
    105.     }
    106.     return 0;
    107. }

            另外为何我这个会超时

    1. // Problem: G. Unusual Entertainment
    2. // Contest: Codeforces - Codeforces Round 909 (Div. 3)
    3. // URL: https://codeforces.com/contest/1899/problem/G
    4. // Memory Limit: 256 MB
    5. // Time Limit: 3000 ms
    6. // 
    7. // Powered by CP Editor (https://cpeditor.org)
    8.  
    9. #include 
    10. using namespace std;
    11. #define LL long long
    12. #define pb push_back
    13. #define x first
    14. #define y second 
    15. #define endl '\n'
    16. const LL maxn = 4e05+7;
    17. const LL N=1e05+10;
    18. const LL mod=1e09+7;
    19. typedef pair<int,int>pl;
    20. priority_queue, greater >t;
    21. priority_queue q;
    22. LL gcd(LL a, LL b){
    23. 	return b > 0 ? gcd(b , a % b) : a;
    24. }
    25. LL lcm(LL a , LL b){
    26. 	return a / gcd(a , b) * b;
    27. }
    28. int n , m;
    29. int a[N] , pos[N];
    30. vector<int>tr[N + 5];
    31. vectorint , 3 > >que[N];
    32. int vis[N];
    33. void init(int n){
    34. 	for(int i = 0 ; i <= n ; i ++){
    35. 		a[i] = 0 , tr[i].clear() , que[i].clear() , vis[i] = 0;
    36. 	}
    37. }
    38. LL l[N] , r[N] , id[N] , sz[N] , hs[N] , tot = 0 , ans[N];
    39. set<int>num;
    40. void dfs(int cur , int f){//重儿子 , 子树大小 
    41. 	l[cur] = ++ tot;
    42. 	id[tot] = cur;//
    43. 	sz[cur] = 1;
    44. 	hs[cur] = -1;
    45. 	for(auto it : tr[cur]){
    46. 		if(it != f){
    47. 			dfs(it , cur);
    48. 			sz[cur] += sz[it];
    49. 			if(hs[cur] == -1 || sz[it] > sz[hs[cur]]){
    50. 				hs[cur] = it;
    51. 			}
    52. 		}		
    53. 	} 
    54. 	r[cur] = tot;
    55. }
    56. void dfs2(int cur , int f , int keep){
    57. 	for(auto it : tr[cur]){
    58. 		if(it != f && it != hs[cur]){
    59. 			dfs2(it , cur , 0);//轻儿子的信息无需保留
    60. 		}
    61. 	}
    62. 	if(hs[cur] != -1){
    63. 		dfs2(hs[cur] , cur , 1);
    64. 	}
    65. 	auto add = [&](int x){
    66. 		vis[x] = 1;
    67. 		num.insert(pos[x]);
    68. 	};
    69. 	auto del = [&](int x){
    70. 		vis[x] = 0;
    71. 		num.erase(pos[x]);
    72. 	};
    73. 	for(auto it : tr[cur]){
    74. 		if(it != f && it != hs[cur]){//轻儿子加入到重儿子当中
    75. 			for(int x = l[it] ; x <= r[it] ; x ++){
    76. 				if(!vis[id[x]])
    77. 					add(id[x]);
    78. 			}
    79. 		}
    80. 	}
    81. 	add(cur);
    82. 	for(auto it : que[cur]){//QLOGN
    83. 		auto  p = lower_bound(num.begin() , num.end() , it[0]);
    84. 		int x = *p;
    85. 	//	cout << cur <<" " << it[0] <<" "<< x << endl;
    86. 		if(x > it[1] || x < it[0]){
    87. 			ans[it[2]] = 0;
    88. 		}
    89. 		else{
    90. 			ans[it[2]] = 1;
    91. 		}
    92. 	}
    93. 	if(!keep){
    94. 		for(int x = l[cur] ; x <= r[cur] ; x ++){//NlogN
    95. 			del(id[x]);
    96. 		}
    97. 	}
    98. }
    99. void solve() 
    100. {
    101. 	cin >> n >> m;
    102. 	for(int i = 1 ; i < n ; i++){
    103. 		int x , y;
    104. 		cin >> x >> y;
    105. 		tr[x].pb(y);
    106. 		tr[y].pb(x);
    107. 	}
    108. 	for(int i = 1 ; i <= n ; i ++){
    109. 		cin >> a[i];
    110. 		pos[a[i]] = i;
    111. 	}
    112. 	for(int i = 0 ; i < m ; i ++){
    113. 		int l , r , x;
    114. 		cin >> l >> r >> x;
    115. 		que[x].pb({l , r , i});
    116. 	}
    117. 	dfs(1 , 0);
    118. 	dfs2(1 , 0 , 0);
    119. 	for(int i = 0 ; i < m ; i ++){
    120. 		if(ans[i]){
    121. 			cout <<"YES\n";
    122. 		}
    123. 		else{
    124. 			cout <<"NO\n";
    125. 		}
    126. 	}
    127. 	init(n);
    128. 	cout << endl;
    129. 	num.clear();
    130. }            
    131. int main() 
    132. {
    133.     ios::sync_with_stdio(false);
    134.     cin.tie(0);
    135.     cout.tie(0);
    136.     cout.precision(10);
    137.     int t=1;
    138. 	cin>>t;
    139.     while(t--)
    140.     {
    141.     	solve();
    142.     }
    143.     return 0;
    144. }

     

  • 相关阅读:
    美格智能5G模组SRM815助力新石器无人车火爆进博会
    【前端】前端CSS整理
    六要素一体微型气象站介绍
    【图像分类】2022-RepLKNet CVPR 31x31卷积了解一下
    深夜测评：讯飞星火大模型vs FuncGPT (慧函数)，到底哪家强？
    基于FTP协议的文件上传与下载
    基于像素预测和位平面压缩的加密图像可逆数据隐藏附matlab代码（论文复现）
    计算机专业毕业设计项目推荐07-科研成果管理系统（JavaSpringBoot+Vue+Mysql）
    数据结构-链表（3）
    Java EE初阶---模板引擎
  • 原文地址：https://blog.csdn.net/weixin_61825750/article/details/134473287