树的统计
源程序名
:count.
pas/c/cpp
可执行文件名
: count.exe
输入文件名
:count.in
输出文件名
: count.out
时限
: 2s
一棵树上有
n
个节点，编号分别为
1
到
n
，每个节点都有一个权值
w
。
我们将以下面的形式来要求你对这棵树完成一些操作：
I.
CHANGE u t :
把结点
u
的权值改为
t
II.
QMAX u v:
询问从点
u
到点
v
的路径上的节点的最大权值
III.
QSUM u v:
询问从点
u
到点
v
的路径上的节点的权值和
注意：从点
u
到点
v
的路径上的节点包括
u
和
v
本身
输入：
输入文件的第一行为一个整数
n
，表示节点的个数。
接下来
n
– 1
行，每行
2
个整数
a
和
b
，表示节点
a
和节点
b
之间有一条边相连。
接下来
n
行，每行一个整数，第
i
行的整数
wi
表示节点
i
的权值。
接下来
1
行，为一个整数
q
，表示操作的总数。
接下来
q
行，每行一个操作，以“
CHANGE u t
”或者“
QMAX u v
”或者“
QSUM u v
”的形式给出。
对于
100
％的数据，保证
1<=n<=30000
，
0<=q<=200000
；中途操作中保证每个节点的权值
w
在
-30000
到
30000
之间。
输出：
对于每个“
QMAX
”或者“
QSUM
”的操作，每行输出一个整数表示要求输出的结果。
样例
count.in
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
count.out
4
1
2
2
10
6
5
6
5
16
标程：//DynamicTrees by using self-adjusting tree
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxN = 30010;
class SplayTree { //So-called LinkCut-Trees
public:
SplayTree *father, *left, *right;
int maxCost, cost, sum;
void Set() {
father = left = right = 0;
}
void UpDate() {
maxCost = sum = cost;
if (left) {
maxCost >?= left->maxCost;
sum += left->sum;
}
if (right) {
maxCost >?= right->maxCost;
sum += right->sum;
}
}
void Zig() {
if (father->father) {
if (father->father->left == father) father->father->left = this;
else if (father->father->right == father) father->father->right = this;
}
father->left = right;
if (right) right->father = father;
right = father;
father = right->father;
right->father = this;
right->UpDate();
UpDate();
}
void Zag() {
if (father->father) {
if (father->father->left == father) father->father->left = this;
else if (father->father->right == father) father->father->right = this;
}
father->right = left;
if (left) left->father = father;
left = father;
father = left->father;
left->father = this;
left->UpDate();
UpDate();
}
void Splay() {
while (father && (father->left == this || father->right == this)) {
if (!father->father || father->father->left != father && father->father->right != father) {
if (father->left == this) Zig();
else Zag();
return;
}
if (father->father->left == father) {
if (father->left == this) {father->Zig(); Zig();}
else {Zag(); Zig();}
}
else if (father->left == this) {Zig();Zag();}
else {father->Zag();Zag();}
}
}
} tree[maxN];
struct dataType {
int nxt, node;
} data[maxN << 1];
int totCases;
int head[maxN], edge[maxN];
bool v[maxN];
int n, dataL;
void Init();
void Dfs(int now);
void Add(int n1, int n2);
void Work();
int Query(int a, int b, int kind);
void Change(int i, int ti);
int main()
{
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
Init();
Dfs(0);
Work();
}
void Init()
{
memset(head, -1, sizeof(head));
scanf("%d", &n);
dataL = 0;
for (int i(1); i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a, --b;
Add(a, b), Add(b, a);
}
for (int i(0); i != n; ++i) tree[i].Set();
for (int i(0); i != n; ++i) {
scanf("%d", &tree[i].cost);
tree[i].maxCost = tree[i].sum = tree[i].cost;
}
}
void Add(int n1, int n2)
{
data[dataL].node = n2;
data[dataL].nxt = head[n1];
head[n1] = dataL;
dataL++;
}
void Dfs(int now)
{
v[now] = true;
for (int tem(head[now]); tem != -1; tem = data[tem].nxt)
if (!v[data[tem].node]) {
tree[data[tem].node].father = &tree[now];
Dfs(data[tem].node);
}
v[now] = false;
}
void Work()
{
int q, a, b;
char ch[20];
scanf("%d", &q);
for (int i(0); i < q; ++i) {
scanf("%s", ch);
scanf("%d%d", &a, &b);
if (ch[0] == 'Q') {
if (ch[1] == 'M') printf("%d\n", Query(a, b, 0));
else printf("%d\n", Query(a, b, 1));
}
else Change(a, b);
}
}
int Query(int a, int b, int kind)
{
int ret1, ret2;
//ACCESS(a)
SplayTree *u = &tree[a - 1], *v = 0;
while (u) {
u->Splay();
u->right = v;
if (v) v->father = u;
u->UpDate();
v = u;
u = u->father;
}
//ACCESS(b)
u = &tree[b - 1], v = 0;
while (u) {
u->Splay();
if (!u->father) {
ret1 = ret2 = u->cost;
if (v) ret1 >?= v->maxCost, ret2 += v->sum;
if (u->right) ret1 >?= u->right->maxCost, ret2 += u->right->sum;
}
u->right = v;
if (v) v->father = u;
u->UpDate();
v = u;
u = u->father;
}
if (!kind) return ret1;
else return ret2;
}
void Change(int i, int ti)
{
tree[i - 1].cost = ti;
tree[i - 1].UpDate();
SplayTree *tem = &tree[i - 1];
while (tem->father && (tem->father->left == tem || tem->father->right == tem)) {
tem = tem->father;
tem->UpDate();
}
}
posted on 2009-03-14 18:43
250 阅读(198)
评论(0) 编辑 收藏 引用