【树链剖分/线段树】BZOJ1036-[ZJOI2008]树的统计Count

【题目大意】

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

【思路】

我来兑现继续做ZJOI2008的flag了。裸的树链剖分，不说什么。但是!主意权值可以为负数，可以为负数！！所以初始化的时候max不是-1，而是要记得清成-INF。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 const int MAXN=+;

 const int INF=0x7fffffff;

 vector<int> E[MAXN];

 int fa[MAXN],dep[MAXN],size[MAXN],son[MAXN];

 int top[MAXN],pos[MAXN];

 int w[MAXN];

 int cnt=,n;

 int sum[MAXN<<],maxn[MAXN<<];

 char str[];

 /*线段树部分*/

 void pushup(int rt)

 {

     sum[rt]=sum[rt<<]+sum[rt<<|];

     maxn[rt]=max(maxn[rt<<],maxn[rt<<|]);

 }

 void modify(int pos,int delta,int l,int r,int rt)

 {

     if (l==r)

     {

         sum[rt]=maxn[rt]=delta;

         return;

     }

     int m=(l+r)>>;

     if (pos<=m) modify(pos,delta,lson);

     if (pos>m) modify(pos,delta,rson);

     pushup(rt);

 }

 int query(int sign,int L,int R,int l,int r,int rt)

 {

     if (L<=l && r<=R)

     {

         if (sign==) return sum[rt];else return maxn[rt];

     }

     int m=(l+r)>>;

     if (sign==)

     {

         int ret=;

         if (L<=m) ret+=query(sign,L,R,lson);

         if (R>m) ret+=query(sign,L,R,rson);

         return ret;

     }

     else

     {

         int res=-INF;

         if (L<=m) res=max(res,query(sign,L,R,lson));

         if (R>m) res=max(res,query(sign,L,R,rson));

         return res;

     }

 }

 /*树链剖分部分*/

 void addedge(int u,int v)

 {

     E[u].push_back(v);

     E[v].push_back(u);

 }

 void dfs1(int u,int pre,int d)

 {

     fa[u]=pre;

     dep[u]=d;

     size[u]=;

     int tmpmax=,hson=-;

     for (int i=;i<E[u].size();i++)

     {

         int to=E[u][i];

         if (to==pre) continue;

         dfs1(to,u,d+);

         if (size[to]>tmpmax)

         {

             tmpmax=size[to];

             hson=to;

         }

         size[u]+=size[to];

     }

     son[u]=hson;

 }

 void dfs2(int u,int t)

 {

     pos[u]=++cnt;

     top[u]=t;

     if (son[u]==-) return;

     dfs2(son[u],t);

     for (int i=;i<E[u].size();i++)

         if (E[u][i]!=son[u] && E[u][i]!=fa[u]) dfs2(E[u][i],E[u][i]);

 }

 int Que(int sign,int u,int v)

 {

     int ans;

     if (sign==) ans=;else ans=-INF;

     int f1=top[u],f2=top[v];

     while (f1!=f2)

     {

         if (dep[f1]<dep[f2])

         {

             swap(f1,f2);

             swap(u,v);

         }

         if (sign==) ans+=query(,pos[f1],pos[u],,n,);

             else ans=max(ans,query(,pos[f1],pos[u],,n,));

         u=fa[f1];

         f1=top[u];

     }

     if (dep[u]>dep[v]) swap(u,v);

     if (sign==) ans+=query(,pos[u],pos[v],,n,);

             else ans=max(ans,query(,pos[u],pos[v],,n,));

     return ans;

 }

 /*主程序部分*/

 void init()

 {

     scanf("%d",&n);

     for (int i=;i<n-;i++)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         addedge(a,b);

     }

     dfs1(,,);

     dfs2(,);

 } 

 void get_ans()

 {

     for (int i=;i<=n;i++)

     {

         scanf("%d",&w[i]);

         modify(pos[i],w[i],,n,);

     }

     int q;

     scanf("%d",&q);

     for (int i=;i<q;i++)

     {

         int u,v;

         scanf("%s%d%d",str,&u,&v);

         if (str[]=='C') modify(pos[u],v,,n,);

         if (str[]=='Q' && str[]=='S') cout<<Que(,u,v)<<endl;

         if (str[]=='Q' && str[]=='M') cout<<Que(,u,v)<<endl;

     }

 }

 int main()

 {

     init();

     get_ans();

     return ;

 }

巴特西

【树链剖分/线段树】BZOJ1036-[ZJOI2008]树的统计Count

最新文章

热门文章