[USACO11DEC]Grass Planting

题目大意：
有一棵结点个数为n的树，有m个操作，可以将一段路径上每条边的权值+1或询问某一个边的权值。

思路：
树链剖分+线段树。
轻重链划分本身比较简单，主要需要思考如何用线段树维护每条链。
当x,y不在同一条链上时，先处理深度大的链，对于每一个链，建立一棵动态开点的线段树，用一个数组len顺序记录每一条边在链中的编号，然后维护len[x]+1到len[top[x]]这一区间的权值即可。
处理轻边时，可以直接用一个数组保存它的权值。
因为轻重边肯定是交替的，因此每次循环都可以先维护一个重边，再维护一个轻边。
最后x和y肯定会跳到同一条重链上，这时候我们只要维护这条链上从len[x]+1到len[y]的边权即可（实际上就是一个找LCA的过程）。
询问则比较简单，因为询问的是一条边而非一条路径，因此直接分类讨论这条边是轻边还是重边即可。（网上那么多题解都是没有读题吗？）

细节：
轻边不能直接对边上某一点开线段树维护，因为如果这个点刚好是某一个重链的第一个点，就会出现轻重边共用同一棵线段树的情况。
这题是USACO月赛题，官方题解是用树状数组维护，但是他们是对整棵树开树状数组，所以还是没我跑得快。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 inline int getint() {

     char ch;

     while(!isdigit(ch=getchar()));

     int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int V=;

 std::vector<int> e[V];

 inline void add_edge(const int u,const int v) {

     e[u].push_back(v);

 }

 class SegmentTree {

     private:

         int val[V<<],left[V<<],right[V<<];

         int sz;

         int newnode() {

             return ++sz;

         }

     public:

         int root[V];

         void modify(int &p,const int b,const int e,const int l,const int r) {

             if(!p) p=newnode();

             if((b==l)&&(e==r)) {

                 val[p]++;

                 return;

             }

             int mid=(b+e)>>;

             if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r));

             if(r>mid) modify(right[p],mid+,e,std::max(mid+,l),r);

         }

         int query(int &p,const int b,const int e,const int x) {

             if(!p) return ;

             if(b==e) return val[p];

             int mid=(b+e)>>;

             return (x<=mid?query(left[p],b,mid,x):query(right[p],mid+,e,x))+val[p];

         }

 };

 SegmentTree t;

 int size[V],son[V],top[V],len[V],dep[V],par[V];

 void dfs1(const int x,const int p) {

     size[x]=;

     dep[x]=dep[p]+;

     par[x]=p;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i];

         if(y==p) continue;

         dfs1(y,x);

         size[x]+=size[y];

         if(size[y]>size[son[x]]) son[x]=y;

     }

 }

 void dfs2(const int x) {

     top[x]=(x==son[par[x]])?top[par[x]]:x;

     for(unsigned i=;i<e[x].size();i++) {

         int &y=e[x][i];

         if(y==par[x]) continue;

         dfs2(y);

         len[x]=len[son[x]]+;

     }

 }

 int val[V];

 inline void modify(int x,int y) {

     while(top[x]!=top[y]) {

         if(dep[top[x]]<dep[top[y]]) std::swap(x,y);

         if(x!=top[x]) t.modify(t.root[top[x]],,len[top[x]],len[x]+,len[top[x]]);

         val[top[x]]++;

         x=par[top[x]];

     }

     if(x==y) return;

     if(dep[x]<dep[y]) std::swap(x,y);

     t.modify(t.root[top[x]],,len[top[x]],len[x]+,len[y]);

 }

 inline int query(int x,int y) {

     if(dep[x]<dep[y]) std::swap(x,y);

     return top[x]==top[y]?t.query(t.root[top[x]],,len[top[x]],len[y]):val[x];

 }

 int main() {

     int n=getint(),m=getint();

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

         int u=getint(),v=getint();

         add_edge(u,v);

         add_edge(v,u);

     }

     dfs1(,);

     dfs2();

     while(m--) {

         char op[];

         scanf("%s",op);

         int x=getint(),y=getint();

         if(op[]=='P') {

             modify(x,y);

         }

         else {

             printf("%d\n",query(x,y));

         }

     }

     return ;

 }

巴特西

[USACO11DEC]Grass Planting

最新文章

热门文章