Problem - D - Codeforces

?

李華有一個(gè)有n個(gè)頂點(diǎn)和n -1條邊的樹(shù)。樹(shù)的根是頂點(diǎn)1。每個(gè)頂點(diǎn)i的重要性為a。將子樹(shù)的大小表示為該子樹(shù)中頂點(diǎn)的數(shù)量，將重要性表示為該子樹(shù)中頂點(diǎn)的重要性之和。將非葉頂點(diǎn)的重子結(jié)點(diǎn)表示為具有最大子樹(shù)大小的子結(jié)點(diǎn)。如果存在多個(gè)重子，則重子的指數(shù)最小。李華想做m個(gè)操作:“1 x”(1≤x≤n) -計(jì)算根為x的子樹(shù)的重要性。"2 x"(2≤x≤n) -旋轉(zhuǎn)z的重子。形式上，表示son為a的重子，fa為z的父親。他想去掉和fa之間的邊，并在son和fa之間連接一條邊。可以保證z不是根結(jié)點(diǎn)，但不能保證z不是葉結(jié)點(diǎn)。如果是葉，請(qǐng)忽略該操作。假設(shè)你是李華，請(qǐng)解決這個(gè)問(wèn)題。輸入第一行包含2個(gè)整數(shù)n, m (2<n <105, 1 < m <105) -樹(shù)中的頂點(diǎn)數(shù)和操作數(shù)。第二行包含n個(gè)整數(shù)a1, a2，…， an(-10°< ai < 10°)-每個(gè)頂點(diǎn)的重要性。接下來(lái)的n -1行包含樹(shù)的邊。第i行包含兩個(gè)整數(shù)ui和vi (1 < ui, vi≤n, ui vi) -對(duì)應(yīng)的邊。給定的邊構(gòu)成了一棵樹(shù)。接下來(lái)的m行包含操作——每行一個(gè)操作。第j個(gè)操作包含兩個(gè)整數(shù)tj, 2;(t, E [1,2)， 1 S a;<n, xj 1如果t;= 2) -第j次操作。輸出對(duì)于每個(gè)“1 ?”查詢(xún)，在獨(dú)立的行中輸出答案。例子

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

題解:

純模擬,只能說(shuō)看懂題意就很簡(jiǎn)單

對(duì)于操作1,就是輸出子樹(shù)權(quán)值和,

操作2,說(shuō)的很麻煩,簡(jiǎn)單來(lái)說(shuō)就是

找到這個(gè)節(jié)點(diǎn)x的父節(jié)點(diǎn)f,找到這個(gè)節(jié)點(diǎn)x的子節(jié)點(diǎn)ne(包含最多子節(jié)點(diǎn)的節(jié)點(diǎn),如果最大的有一樣的,找標(biāo)號(hào)最小的)

找到后f與x斷開(kāi),f與ne連邊,ne與x連邊

對(duì)于子樹(shù)權(quán)值和,很好計(jì)算,

關(guān)鍵是如何找到這個(gè)節(jié)點(diǎn)x的子節(jié)點(diǎn)ne(包含最多子節(jié)點(diǎn)的節(jié)點(diǎn),如果最大的有一樣的,找標(biāo)號(hào)最小的)

因此對(duì)于每個(gè)節(jié)點(diǎn),dfs記錄每個(gè)子樹(shù)權(quán)值的同時(shí),并且記錄子樹(shù)大小

我們利用set進(jìn)行存儲(chǔ)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn),{-son[x],x}

-son[x],每次可以取出節(jié)點(diǎn)最多的子節(jié)點(diǎn),同時(shí)set保證了下標(biāo)從小到大,每次取首位即可

接下來(lái)就是維護(hù),三個(gè)節(jié)點(diǎn)子樹(shù)權(quán)值,子樹(shù)大小,父節(jié)點(diǎn)(麻煩,但是很容易理解,代碼中均有體現(xiàn))

(如果操作2操作的是葉子結(jié)點(diǎn),記得按題中所說(shuō)的跳過(guò))文章來(lái)源地址http://www.zghlxwxcb.cn/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(); 
	}
}

到了這里，關(guān)于D. Li Hua and Tree(set操作)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！