[ZJOI2008]树的统计Count

[ZJOI2008]树的统计Count

Time Limit:10000MS  Memory Limit:165536K
Total Submit:116 Accepted:61
Case Time Limit:1000MS

Description

一棵树上有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本身

Input

输入的第一行为一个整数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之间。

Output

对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

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

Sample Output

4
1
2
2
10
6
5
6
5
16

Source
额。。我的算法极慢,卡着时间过了。。
一般的算法就是Link—Cut树,树链剖分啊什么的,由于我太菜,只好想了个很SB的算法,我想的是可以不可以用类似于块状数组的办法来解决这道题目。。那么把这个树分成Sqrt(N)左右的小块,然后每次往上跳。。可以在Sqrt(N)中解决问题。。关键是怎么划分。。我TLE了N次主要就是在尝试划分的办法囧。。搞了半天最后稀里糊涂弄出来了。。我真是菜死了囧。。。
改进了一下Code。。变快一点了。。
Code:

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int inf=~0U>>1,maxn=30000;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],Lim,dep[maxn],Fa[maxn];
int own[maxn],Max[maxn],Sum[maxn]={};
void Build(int t,int f,int d)
{
dep[t]=d;Fa[t]=f;
if(own[t]==-1)
{
own[t]=t;
Sum[t]++;
}
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(Sum[tmp]<Lim)
{
Et[t].pb(*e);
own[*e]=tmp;
Sum[tmp]++;
}
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
Sum[t]=s+=w[t];Max[t]=m=max(m,w[t]);
tr(e,Et[t])Dfs(*e,s,m);
}
void Change(int t,int u)
{
w[t]=u;
if(t==own[t])Dfs(t,0,-inf);
else Dfs(t,Sum[Fa[t]],Max[Fa[t]]);
}
int QSum(int a,int b)
{
int s=0;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b]||own[a]==a)
s+=w[a],a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
s+=Sum[a],a=Fa[own[a]];
}
}
return s+w[a];
}
int QMax(int a,int b)
{
int m=-inf;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b])
m=max(m,w[a]),a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
m=max(m,Max[a]),a=Fa[own[a]];
}
}
return max(m,w[a]);
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);int s,t;Lim=sqrt(n)+1;
rep(i,n-1)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)scanf("%d",w+i);
memset(own,-1,sizeof own);
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else if(cmd[1]==’S’)printf("%dn",QSum(s-1,t-1));
else printf("%dn",QMax(s-1,t-1));
}
}

46 thoughts on “[ZJOI2008]树的统计Count

  1. 我怎么这么若!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

  2. 回复Apocalypse9:囧。。我这两天正在外面旅游。。。过几天写个详细点的说明好了。。不过我发现这个数据结构很悲剧的。。就叫它块状树好了(效仿块状数组)。。这玩意除了代码量小点之外没有任何有点,无论是复杂度还是功能都不及动态树和树链剖分。。只能用来偷懒囧。。。

  3. I’m really enjoying the theme/design of your blog.

    Do you ever run into any web browser compatibility issues?
    A handful of my blog visitors have complained about
    my blog not working correctly in Explorer but looks great
    in Opera. Do you have any advice to help fix this issue?

  4. Hi I am so thrilled I found your blog page, I really found you by mistake,
    while I was looking on Yahoo for something else, Anyhow I am here now and would just like to say kudos for a marvelous post and
    a all round enjoyable blog (I also love the theme/design), I dont have time
    to read it all at the moment but I have bookmarked it
    and also added your RSS feeds, so when I have time I will be back to read more, Please
    do keep up the awesome jo.

    Here is my page :: ElmerNPrewer

  5. This is the perfect site for anybody who hopes to find out about
    this topic. You realize so much its almost
    hard to argue with you (not that I really would want toHaHa).
    You certainly put a fresh spin on a topic which has been written about for years.
    Great stuff, just great!

    Feel free to surf to my blog post IsrealKAcoba

  6. We prefer to honor quite a few other web websites around the internet, even though they arent linked to us, by linking to them. Underneath are some webpages really worth checking out.

  7. we like to honor many other world-wide-web sites around the net, even when they arent linked to us, by linking to them. Below are some webpages really worth checking out

  8. we prefer to honor a lot of other web web sites on the web, even though they arent linked to us, by linking to them. Beneath are some webpages really worth checking out

  9. we like to honor lots of other internet internet sites around the internet, even when they arent linked to us, by linking to them. Below are some webpages worth checking out

  10. we like to honor several other online web sites around the internet, even when they arent linked to us, by linking to them. Beneath are some webpages worth checking out

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>