D. Li Hua and Tree(set操作)-Toy模板网

这篇具有很好参考价值的文章主要介绍了D. Li Hua and Tree(set操作)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem - D - Codeforces

D. Li Hua and Tree(set操作)

李华有一个有n个顶点和n -1条边的树。树的根是顶点1。每个顶点i的重要性为a。将子树的大小表示为该子树中顶点的数量，将重要性表示为该子树中顶点的重要性之和。将非叶顶点的重子结点表示为具有最大子树大小的子结点。如果存在多个重子，则重子的指数最小。李华想做m个操作:“1 x”(1≤x≤n) -计算根为x的子树的重要性。"2 x"(2≤x≤n) -旋转z的重子。形式上，表示son为a的重子，fa为z的父亲。他想去掉和fa之间的边，并在son和fa之间连接一条边。可以保证z不是根结点，但不能保证z不是叶结点。如果是叶，请忽略该操作。假设你是李华，请解决这个问题。输入第一行包含2个整数n, m (2<n <105, 1 < m <105) -树中的顶点数和操作数。第二行包含n个整数a1, a2，…， an(-10°< ai < 10°)-每个顶点的重要性。接下来的n -1行包含树的边。第i行包含两个整数ui和vi (1 < ui, vi≤n, ui vi) -对应的边。给定的边构成了一棵树。接下来的m行包含操作——每行一个操作。第j个操作包含两个整数tj, 2;(t, E [1,2)， 1 S a;<n, xj 1如果t;= 2) -第j次操作。输出对于每个“1 æ”查询，在独立的行中输出答案。例子

Examples

input

Copy

7 4
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
6 7
1 6
2 3
1 6
1 2

output

Copy

2
3
3

input

Copy

10 14
-160016413 -90133231 -671446275 -314847579 -910548234 121155052 -359359950 83112406 -704889624 145489303
1 6
1 10
10 8
1 4
3 4
2 7
2 5
3 2
9 8
1 4
2 2
2 4
1 4
1 10
2 10
1 9
1 6
2 8
2 10
1 5
1 8
1 1
2 5

output

Copy

-2346335269
-314847579
-476287915
-704889624
121155052
-1360041415
228601709
-2861484545

题解:

纯模拟,只能说看懂题意就很简单

对于操作1,就是输出子树权值和,

操作2,说的很麻烦,简单来说就是

找到这个节点x的父节点f,找到这个节点x的子节点ne(包含最多子节点的节点,如果最大的有一样的,找标号最小的)

找到后f与x断开,f与ne连边,ne与x连边

对于子树权值和,很好计算,

关键是如何找到这个节点x的子节点ne(包含最多子节点的节点,如果最大的有一样的,找标号最小的)

因此对于每个节点,dfs记录每个子树权值的同时,并且记录子树大小

我们利用set进行存储每个节点的子节点,{-son[x],x}

-son[x],每次可以取出节点最多的子节点,同时set保证了下标从小到大,每次取首位即可

接下来就是维护,三个节点子树权值,子树大小,父节点(麻烦,但是很容易理解,代码中均有体现)

(如果操作2操作的是叶子结点,记得按题中所说的跳过)文章来源地址https://www.toymoban.com/news/detail-411858.html

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
vector<int> p[100050];
int n,m;
int sum[100050];
int son[100060];
int fa[100050];
int a[100050];
set <PII> d[100050];
void dfs(int x,int la)
{
	sum[x] = a[x];
	son[x] = 1;
	for(auto ne:p[x])
	{
		if(ne == la)
		continue;
		dfs(ne,x);
		sum[x] += sum[ne];
		son[x] += son[ne];
		fa[ne] = x;
		d[x].insert({-son[ne],ne});
	}
}
void solve()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i]; 
	}
	for(int i = 1;i < n;i++)
	{
		int l,r;
		cin >> l >> r;
		p[l].push_back(r);
		p[r].push_back(l);
	}
	dfs(1,0);
	while(m--)
	{
		int op,x;
		cin >> op >> x;
		if(op == 1)
		{
			cout << sum[x] <<"\n";
		}
		else
		{
			if(son[x] == 1)
			continue;
			int f = fa[x];
			auto it = d[x].begin();
			int ne = (*it).second;
			d[f].erase({-son[x],x});
			sum[x] -= sum[ne];
			son[x] -= son[ne];
			d[x].erase(*it);
			d[ne].insert({-son[x],x});
			fa[ne] = f;
			fa[x] = ne;
			sum[ne] += sum[x];
			son[ne] += son[x];
			d[f].insert({-son[ne],ne});
		}
	}
}

signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve(); 
	}
}

到了这里，关于D. Li Hua and Tree(set操作)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！