樹的統(tǒng)計
??????????????????????????????????????????????????????????
源程序名
:count.
pas/c/cpp
可執(zhí)行文件名
: count.exe
輸入文件名
:count.in
輸出文件名
: count.out
時限
: 2s
?
一棵樹上有
n
個節(jié)點，編號分別為
1
到
n
，每個節(jié)點都有一個權(quán)值
w
。
我們將以下面的形式來要求你對這棵樹完成一些操作：
I.??????????????????
CHANGE u t :
把結(jié)點
u
的權(quán)值改為
t
II.???????????????
QMAX u v:
詢問從點
u
到點
v
的路徑上的節(jié)點的最大權(quán)值
III.????????????
QSUM u v:
詢問從點
u
到點
v
的路徑上的節(jié)點的權(quán)值和
?
注意：從點
u
到點
v
的路徑上的節(jié)點包括
u
和
v
本身
?
輸入：
輸入文件的第一行為一個整數(shù)
n
，表示節(jié)點的個數(shù)。
??????
接下來
n
– 1
行，每行
2
個整數(shù)
a
和
b
，表示節(jié)點
a
和節(jié)點
b
之間有一條邊相連。
??????
接下來
n
行，每行一個整數(shù)，第
i
行的整數(shù)
wi
表示節(jié)點
i
的權(quán)值。
??????
接下來
1
行，為一個整數(shù)
q
，表示操作的總數(shù)。
接下來
q
行，每行一個操作，以“
CHANGE u t
”或者“
QMAX u v
”或者“
QSUM u v
”的形式給出。
?
對于
100
％的數(shù)據(jù)，保證
1<=n<=30000
，
0<=q<=200000
；中途操作中保證每個節(jié)點的權(quán)值
w
在
-30000
到
30000
之間。
輸出：
??????
對于每個“
QMAX
”或者“
QSUM
”的操作，每行輸出一個整數(shù)表示要求輸出的結(jié)果。
樣例
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 閱讀(200)
評論(0) 編輯 收藏 引用