D. Li Hua and Tree(set操作)

Problem - D - Codeforces

李华有一个有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操作的是叶子结点,记得按题中所说的跳过)

#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(); }
}