精华内容
下载资源
问答
  • 反正先求一遍sa 然后这个问题可以稍微转化一下 默认比较A、B数组中元素大小都是比较它们rank大小,毕竟两个位置LCP就是它们rankrmq 然后每次只要求B[j]>...=A[i]的怎么算 排序以后从后往前推着做...

    反正先求一遍sa

    然后这个问题可以稍微转化一下

    默认比较A、B数组中元素的大小都是比较它们rank的大小,毕竟两个位置的LCP就是它们rank的rmq

    然后每次只要求B[j]>=A[i]的LCP(B[j],A[i]),然后再求A[j]>B[i]的LCP(A[j],B[i])即可

    这两个其实是差不多的,下面只说B[j]>=A[i]的怎么算

    排序以后从后往前推着做(当然从前往后也行)

    用一个权值线段树记下来LCP(A[i],B[j])==x的B[j]的数量、以及这个数量*x的和

    然后考虑怎么把它从A[i]转移到A[i-1]

    其实就是对于每个j给LCP(A[i],B[j])和LCP(A[i-1],A[i])取个min,放到权值线段树上,就是把大于LCP(A[i-1],A[i])的都删掉,然后在LCP(A[i-1],A[i])处加上刚才删掉的个数

    所以我推着做的时候,先来取个min,然后把新来的B[j]加到线段树里,每做一个A[i]统计一下线段树整体的和即可

      1 #include<bits/stdc++.h>
      2 #define pa pair<int,int>
      3 #define CLR(a,x) memset(a,x,sizeof(a))
      4 using namespace std;
      5 typedef long long ll;
      6 const int maxn=4e5+10;
      7 
      8 inline ll rd(){
      9     ll x=0;char c=getchar();int neg=1;
     10     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
     11     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
     12     return x*neg;
     13 }
     14 
     15 int N,M,Q;
     16 char s[maxn];
     17 int sa[maxn],rnk[maxn],hei[maxn],rank1[maxn],tmp[maxn],cnt[maxn];
     18 int st[maxn][22];
     19 
     20 inline void getsa(){
     21     int i,j=0,k;
     22     for(i=1;i<=N;i++) cnt[s[i]]=1;
     23     for(i=1;i<=M;i++) cnt[i]+=cnt[i-1];
     24     for(i=N;i;i--) rnk[i]=cnt[s[i]];
     25     
     26     for(k=1;j!=N;k<<=1){
     27         memset(cnt,0,sizeof(cnt));
     28         for(i=1;i<=N;i++) cnt[rnk[i+k>N?0:i+k]]++;
     29         for(i=1;i<=M;i++) cnt[i]+=cnt[i-1];
     30         for(i=N;i;i--) tmp[cnt[rnk[i+k>N?0:i+k]]--]=i;
     31         memset(cnt,0,sizeof(cnt));
     32         for(i=1;i<=N;i++) cnt[rnk[i]]++;
     33         for(i=1;i<=M;i++) cnt[i]+=cnt[i-1];
     34         for(i=N;i;i--) sa[cnt[rnk[tmp[i]]]--]=tmp[i];
     35         memcpy(rank1,rnk,sizeof(rank1));
     36         rnk[sa[1]]=j=1;
     37         for(i=2;i<=N;i++){
     38             if(rank1[sa[i]]!=rank1[sa[i-1]]||rank1[sa[i]+k>N?0:sa[i]+k]!=rank1[sa[i-1]+k>N?0:sa[i-1]+k]) j++;
     39             rnk[sa[i]]=j;
     40         }M=j;
     41     }
     42     for(i=1;i<=N;i++) sa[rnk[i]]=i;
     43 }
     44 
     45 inline void geth(){
     46     for(int i=1,j=0;i<=N;i++){
     47         if(rnk[i]==1) continue;
     48         if(j) j--;
     49         int x=sa[rnk[i]-1];
     50         while(x+j<=N&&i+j<=N&&s[x+j]==s[i+j]) j++;
     51         hei[rnk[i]]=j;
     52     }
     53 }
     54 
     55 inline void getst(){
     56     for(int i=N;i;i--){
     57         st[i][0]=hei[i];
     58         for(int j=1;st[i+(1<<(j-1))][j-1];j++){
     59             st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
     60         }
     61     }
     62 }
     63 
     64 inline int rmq(int l,int r){
     65     if(l>r) return N-sa[r]+1;
     66     int x=log2(r-l+1);
     67     return min(st[l][x],st[r-(1<<x)+1][x]);
     68 }
     69 
     70 ll sum[maxn<<2],siz[maxn<<2];
     71 bool laz[maxn<<2];
     72 
     73 inline void update(int p){sum[p]=sum[p<<1]+sum[p<<1|1],siz[p]=siz[p<<1]+siz[p<<1|1];}
     74 inline void pushdown(int p){
     75     if(!laz[p]) return;
     76     int a=p<<1,b=p<<1|1;
     77     sum[a]=siz[a]=0,laz[a]=1;
     78     sum[b]=siz[b]=0,laz[b]=1;
     79     laz[p]=0;
     80 }
     81 int erase(int p,int l,int r,int x,int y){
     82     if(x<=l&&r<=y){
     83         int re=siz[p];
     84         siz[p]=sum[p]=0;laz[p]=1;
     85         pushdown(p);
     86         return re;
     87     }else{
     88         pushdown(p);
     89         int m=l+r>>1,re=0;
     90         if(x<=m) re=erase(p<<1,l,m,x,y);
     91         if(y>=m+1) re+=erase(p<<1|1,m+1,r,x,y);
     92         update(p);
     93         return re;
     94     }
     95 }
     96 void add(int p,int l,int r,int x,int y){
     97     if(l==r){
     98         siz[p]+=y,sum[p]+=1ll*y*l;
     99     }else{
    100         pushdown(p);
    101         int m=l+r>>1;
    102         if(x<=m) add(p<<1,l,m,x,y);
    103         else add(p<<1|1,m+1,r,x,y);
    104         update(p);
    105     }
    106 }
    107 
    108 inline bool cmp(int a,int b){return rnk[a]<rnk[b];}
    109 
    110 int A[maxn],B[maxn];
    111 ll solve(int k,int l){
    112     sort(A+1,A+k+1,cmp);sort(B+1,B+l+1,cmp);
    113     ll re=0;
    114     for(int i=k,j=l;i;i--){
    115         if(i!=k){
    116             int x=rmq(rnk[A[i]]+1,rnk[A[i+1]]),t=erase(1,0,N,x+1,N);
    117             add(1,0,N,x,t);
    118         }
    119         for(;rnk[B[j]]>=rnk[A[i]]&&j;j--)
    120             add(1,0,N,rmq(rnk[A[i]]+1,rnk[B[j]]),1);
    121         re+=sum[1];
    122     }
    123     erase(1,0,N,0,N);
    124     for(int i=k,j=l;j;j--){
    125         if(j!=l){
    126             int x=rmq(rnk[B[j]]+1,rnk[B[j+1]]),t=erase(1,0,N,x+1,N);
    127             add(1,0,N,x,t);
    128         }
    129         for(;rnk[A[i]]>rnk[B[j]]&&i;i--)
    130             add(1,0,N,rmq(rnk[B[j]]+1,rnk[A[i]]),1);
    131         re+=sum[1];
    132     }
    133     erase(1,0,N,0,N);
    134     return re;
    135 }
    136 
    137 int main(){
    138     //freopen(".in","r",stdin);
    139     int i,j,k;
    140     N=rd(),Q=rd();
    141     scanf("%s",s+1);
    142     M=128;
    143     getsa();geth();getst();
    144     for(i=1;i<=Q;i++){
    145         int a=rd(),b=rd();
    146         for(j=1;j<=a;j++)
    147             A[j]=rd();
    148         for(j=1;j<=b;j++)
    149             B[j]=rd();
    150         printf("%I64d\n",solve(a,b));
    151     }
    152     return 0;
    153 }

     

    转载于:https://www.cnblogs.com/Ressed/p/9863745.html

    展开全文
  • 其实本人学树剖时还完全没到学树剖的水平,但本着在图论这一块的兴趣就...这棵树的红线就是剖出来的链条:特别地,一个点也一条链.  但是问题来了,假如树上有两个点,我怎么知道他们俩是不是在同一条链子上呢...

      其实本人学树剖时还完全没到学树剖的水平,但本着在图论这一块的兴趣就看了看,结果发现树剖还挺简单?

      树剖是什么呢?看看它的全称:“树链剖分”。顾名思义,就是把一棵树解剖成一个个链子咯。然后在每条链上维护需要的信息,比如最小值、最大值、权值和什么的。这棵树的红线就是剖出来的链条:特别地,一个点也算一条链.

     

      但是问题来了,假如树上有两个点,我怎么知道他们俩是不是在同一条链子上呢?所以我们还需要用一个东西来给链子上的所有节点染色,这样就可以回答刚才的问题了。怎么染呢?我们想一个问题,如果我要查树上两个点之间节点的权值的最大值,怎么查?这里就有两种情况:

        1.这两个点在同一条链上,这样的话就可以直接查出链上两点的区间中的最小值了。

        2.这两个点不在同一条链上。我们就可以让两个点不断往上跳,直到跳到他们属于同一条链为止。而树剖的关键之一就是这个跳法。如果朴(bao)素(li)一点,怎么跳?那当然是一个点一个点地往上跳,那么时间复杂度就是O(N),对于m次查询就是O(NM)。那我还要树剖有个屁用。。。所以要换一种优雅点的。现在我们不是把树都剖成链了吗?为什么不一条链一条链地跳呢?我们可以首先记录下当前节点u所在的链的顶端top[u],若要跳出这条链,就让u=fa[top[u]](不是top[u])。就像这样不断地跳,直到两个点的top相同为止。

      以上就是树剖的基本思路。那么我们为什么要树剖这种东西呢?“有时可以用来暴力。”——学校一个大佬。树剖确实是暴力,只不过非常地优雅。如果一道题需要查询树上两点的区间中的某些信息,我们可以直接查这个区间,而不是枚举区间的每个点。所以我们需要记录下树上的每一个区间,用线段树来维护,而这些区间就是上面所说的链条了。这样一来,每次查询的复杂度就降为O(logN)了。当然这是最理想的情况。而为了让我们的树剖的复杂度尽量接近这个等级,我们就需要想办法把树剖成logN条链子。所以这里引入一个概念:重链剖分。

      所谓重链,给人的感觉就是这条链特别重。也就是这条链的节点数特别多了。而重链剖分的过程就是:对于当前节点u,找出以它的子节点为根的子树中节点最多的一棵子树,假如这颗子树的根为v,那么就给这条链加上节点v,并递归下去,对v也如法炮制。这样构造出的链就很接近logN个。而u的这个子节点v有个定义,叫做u的“重儿子”。

      那么,怎么让一条链所表示的区间内的所有节点都是连续的整数呢?想想刚才的操作,我们在建链时是沿着链递归下去的,如果我们这时记下每个节点的时间戳的话,是不是这条链上的时间戳就是一串连续的整数了呢?这样就解决了刚才的问题。所以,我们在剖树时,需要两次DFS,第一次找出每个节点的重儿子,第二次沿着重儿子走下去,记下每个点被遍历到的时间戳:

    void dfs_getson(int u){//第一次DFS
        size[u] = 1;
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to;
            if(v == fa[u]) continue;//注意不能往回走
            fa[v] = u;
            dep[v] = dep[u] + 1;//计算深度,等会要讲.
            dfs_getson(v);
            size[u] += size[v];
            if(size[v] > size[son[u]]) son[u] = v;//记录u的重儿子.
        }
    }
    void dfs_rewrite(int u, int tp){//第二次DFS
        top[u] = tp, dfn[u] = ++tot, id[tot] = u;//id为dfn的反函数,由于链上的区间由dfn组成,为了知道链上某个点的编号我们记录下id.top为u所在链的顶端
        if(son[u]) dfs_rewrite(son[u], tp);//优先往重儿子走.
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to;
            if(v != fa[u] && v != son[u]) dfs_rewrite(v, v);//往不是重儿子的儿子(轻儿子)走
        }
    }

     

      像这样,一棵树就被我们剖成了链。不过这些链现在还没有什么用,我们需要用线段树来维护它们。所以首先是构造。这里用区间最大值为例,其它的类似:

    void build(int d, int l, int r){
        t[d].l = l, t[d].r = r;
        if(l == r){ t[d].mmax = val[id[l]]; return; }//要注意这里的lr都是dfn值
        int mid = l + r >> 1;
        build(d << 1, l, mid);//构造左儿子
        build(d << 1 | 1, mid + 1, r);//构造右儿子
        t[d].mmax = max(t[d << 1].mmax, t[d << 1 | 1].mmax);
    }
    //main函数中
        build(1, 1, tot); 

     

      然后是单点查询:

    int getmax_vertex(int d, int x){
        if(t[d].l == t[d].r) return t[d].mmax;
        int mid = t[d].l + t[d].r >> 1;
        if(x <= mid) return getmax_vertex(d << 1, x);
        else return getmax_vertex(d << 1 | 1, x);
    }
    //main函数中
        ans = getmax_vertex(1, dfn[u]); 

      单点修改:

    void change_vertex(int d, int x, int w){
        if(t[d].l == t[d].r){ t[d].mmax = w; return; }
        int mid = t[d].l + t[d].r >> 1;
        if(x <= mid) change_vertex(d << 1, x, w);
        else change_vertex(d << 1 | 1, x, w);
        t[d].mmax = max(t[d << 1].mmax, t[d << 1 | 1].mmax); 
    }
    //main函数中
        change_vertex(1, dfn[u], w); 

      需要注意的是对区间的操作。其实上面已经提到了,若区间的两个端点u,v在同一条链上,那么直接操作就可以了。而不在一条链上时,只需要跳到同一条链上即可。那么谁跳呢?假如我们让top深度小的点跳,深度只能越跳越小,永远小于另一个点,直到跳到根节点也什么也做不了(可以画个图来理解)。所以我们应该选择top深度大的开始跳,边跳边对跳过的链操作,最后跳到同一条链时再操作一次。

      于是就有了区间查询(延迟标记就懒得写了):

    int getmax_xtoy(int d, int l, int r){
        if(l <= t[d].l && t[d].r <= r) return t[d].mmax;
        if(t[d].f) down(d);
        int mid = t[d].l + t[d].r >> 1, ans = 0;
        if(l <= mid) ans = max(ans, getmax_xtoy(d << 1, l, r));
        if(r > mid) ans = max(ans, getmax_xtoy(d << 1 | 1, l, r));
        return ans;
    }
    //main函数中
        int ans = 0;
        while(top[u] != top[v]){
            if(dep[top[u]] > dep[top[v]]) swap(u, v);//从深度大的开始跳
            ans = max(ans, getmax_xtoy(1, dfn[top[v]], dfn[v]));
            v = fa[top[v]];//注意要调到顶端的父亲去
        }
        if(dep[u] > dep[v]) swap(u, v);
        ans = max(ans, getmax_xtoy(1, dfn[u], dfn[v]));

      以及区间修改:

    void change_xtoy(int d, int l, int r, int w){
        if(l <= t[d].l && t[d].r <= r){ t[d].mmax = w; t[d].f = w; return; }
        if(t[d].f) down(d);
        int mid = t[d].l + t[d].r >> 1;
        if(l <= mid) change_xtoy(d << 1, l, r, w);
        if(r > mid) change_xtoy(d << 1 | 1, l, r, w);
        t[d].mmax = max(t[d << 1].mmax, t[d << 1 | 1].mmax);
    }
    //main函数中
        while(top[u] != top[v]){
            if(dep[top[u]] > dep[top[v]]) swap(u, v);
            change_xtoy(1, dfn[top[v]], dfn[v], w);
            v = fa[top[v]];
        } 
        if(dep[u] > dep[v]) swap(u, v);
        change_xtoy(1, dfn[u], dfn[v]);

      没错,树链剖分就是个码量惊人的东西。


     

      现在我们可以愉快地刷例题了。

    P3384 【模板】树链剖分

    题目描述

    如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

    操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z

    操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和

    操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z

    操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和

    输入输出格式

    输入格式:

    第一行包含4个正整数N、M、R、P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。

    接下来一行包含N个非负整数,分别依次表示各个节点上初始的数值。

    接下来N-1行每行包含两个整数x、y,表示点x和点y之间连有一条边(保证无环且连通)

    接下来M行每行包含若干个正整数,每行表示一个操作,格式如下:

    操作1: 1 x y z

    操作2: 2 x y

    操作3: 3 x z

    操作4: 4 x

    输出格式:

    输出包含若干行,分别依次表示每个操作2或操作4所得的结果(对P取模)

      这不是模板题。这题涉及了区间修改、区间查询,以及——子树修改和查询???这就是这题的难点了。子树并不只是简单的一条链,这怎么办呢?实际上子树的东西还简单地可怜。想想,我们在对区间操作时的对象等同于一些连续的dfn值,而子树呢?子树的所有点的dfn值不也是连续的一串吗?所以我们在第二次搜索时不仅记录下节点x的dfn值,也记下以x为根的子树的dfn最大值:

    void dfs_rewrite(int u, int tp){
        top[u] = tp, dfn[u] = ++tot, id[tot] = u;
        if(son[u]) dfs_rewrite(son[u], tp);
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to;
            if(v != fa[u] && v != son[u]) dfs_rewrite(v, v); 
        }
        cnt[v] = tot;//递归完子树后的tot就是dfn最大值 
    }

      而对子树的操作也就可以写得出来了:

    inline void getsum_sontree(){//查询子树和 
        int u;
        scanf("%d", &u);
        ans = getsum(1, dfn[u], cnt[u]);
    }
    inline void change_sontree(){//修改子树值
        int u, w;
        scanf("%d %d", &u, &w);
        change(1, dfn[u], cnt[u], w);
    }

      最后放上代码(我也不知道用不用long long):

    #include <string.h>
    #include <stdio.h>
    #define maxn 500010
    #define maxm 500010
    
    struct graph{
        struct edge{
            long long to, next;
            edge(){}
            edge(const long long &_to, const long long &_next){
                to = _to;
                next = _next;
            }
        }e[maxn << 1];
        long long head[maxn], k;
        inline void init(){
            memset(head, -1, sizeof head);
            k = 0;
        }
        inline void add(const long long &u, const long long &v){
            e[k] = edge(v, head[u]);
            head[u] = k++;
        }
    }g;
    
    struct node{
        long long l, r, zuo, you;
        long long c, f;
    }t[maxn << 2];
    
    long long fa[maxn], dep[maxn], size[maxn], son[maxn];
    long long dfn[maxn], id[maxn], top[maxn], cnt[maxn], tot;
    long long n, m, root, p, val[maxn], len;
    
    inline void swap(long long &x, long long &y){long long t = x; x = y; y = t;}
    
    void dfs_getson(long long u){
        size[u] = 1;
        for(long long i = g.head[u]; ~i; i = g.e[i].next){
            long long v = g.e[i].to;
            if(v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs_getson(v);
            size[u] += size[v];
            if(size[v] > size[son[u]]) son[u] = v;
        }
    }
    
    void dfs_rewrite(long long u, long long tp){
        top[u] = tp;
        dfn[u] = ++tot;
        id[tot] = u;
        if(son[u]) dfs_rewrite(son[u], tp);
        for(long long i = g.head[u]; ~i; i = g.e[i].next){
            long long v = g.e[i].to;
            if(v != son[u] && v != fa[u]) dfs_rewrite(v, v);
        }
        cnt[u] = tot;
    }
    
    void build(long long d, long long l, long long r){
        t[d].l = l, t[d].r = r;
        if(l == r){
            t[d].c = val[id[l]];
            return;
        }
        long long mid = l + r >> 1;
        build(d << 1, l, mid);
        build(d << 1 | 1, mid + 1, r);
        t[d].c = t[d << 1].c + t[d << 1 | 1].c;
    }
    
    inline void down(long long d){
        t[d << 1].f += t[d].f;
        t[d << 1 | 1].f += t[d].f;
        t[d << 1].c += t[d].f * (t[d << 1].r - t[d << 1].l + 1);
        t[d << 1 | 1].c += t[d].f * (t[d << 1 | 1].r - t[d << 1 | 1].l + 1);
        t[d].f = 0;
    }
    
    void change(long long d, long long l, long long r, long long x){
        if(l <= t[d].l && t[d].r <= r){
            t[d].c += (t[d].r - t[d].l + 1) * x;
            t[d].f += x;
            return;
        }
        if(t[d].f) down(d);
        long long mid = t[d].l + t[d].r >> 1;
        if(l <= mid) change(d << 1, l, r, x);
        if(r > mid) change(d << 1 | 1, l, r, x);
        t[d].c = t[d << 1].c + t[d << 1 | 1].c;
    }
    
    long long getsum(long long d, long long l, long long r){
        if(l <= t[d].l && t[d].r <= r) return t[d].c;
        if(t[d].f) down(d);
        long long mid = t[d].l + t[d].r >> 1;
        long long ans = 0;
        if(l <= mid) ans =  (ans + getsum(d << 1, l, r)) % p;
        if(r > mid) ans = (ans + getsum(d << 1 | 1, l, r)) % p;
        return ans;
    }
    
    inline void change_xtoy(){
        long long x, y, z;
        scanf("%lld%lld%lld",&x, &y, &z);
        while(top[x] != top[y])
        {
            if(dep[top[x]] > dep[top[y]]) swap(x, y);
            change(1, dfn[top[y]], dfn[y], z);
            y = fa[top[y]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        change(1, dfn[x], dfn[y], z); 
    }
    
    inline void getson_xtoy(){
        long long x, y;
        scanf("%lld%lld", &x, &y);
        long long ans = 0;
        while(top[x] != top[y]){
            if(dep[top[x]] > dep[top[y]]) swap(x, y);
            ans = (ans + getsum(1, dfn[top[y]], dfn[y])) % p;
            y = fa[top[y]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        ans += getsum(1, dfn[x], dfn[y]);
        printf("%lld\n", ans % p);
    }
    
    inline void change_sontree(){
        long long x, y;
        scanf("%lld%lld", &x, &y);
        change(1, dfn[x], cnt[x], y);
    }
    
    inline void getsum_sontree(){
        long long x;
        scanf("%lld", &x);
        printf("%lld\n", getsum(1, dfn[x], cnt[x]) % p);
    }
    
    int main(){
        g.init();
        scanf("%lld%lld%lld%lld", &n, &m, &root, &p);
        for(long long i = 1; i <= n; i++) scanf("%lld", &val[i]);
        for(long long i = 1; i < n; i++){
            long long u, v;
            scanf("%lld%lld", &u, &v);
            g.add(u, v);
            g.add(v, u);
        }
        dfs_getson(root);
        dfs_rewrite(root, root);
        build(1, 1, tot);
        for(long long i = 1; i <= m; i++){
            long long op;
            scanf("%lld", &op);
            if(op == 1) change_xtoy();
            if(op == 2) getson_xtoy();
            if(op == 3) change_sontree();
            if(op == 4) getsum_sontree();
        }
        return 0;
    }

      注释应该就不需要了吧,自我感觉代码还是能被看懂的(溜~)


     

    P2146 [NOI2015]软件包管理器

    题目描述

    Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。

    你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,⋯,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,A[m-1]依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。

    现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。

    输入输出格式

    输入格式:

     

    从文件manager.in中读入数据。

    输入文件的第1行包含1个整数n,表示软件包的总数。软件包从0开始编号。

    随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

    接下来一行包含1个整数q,表示询问的总数。之后q行,每行1个询问。询问分为两种:

    install x:表示安装软件包x

    uninstall x:表示卸载软件包x

    你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。

    对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。

     

    输出格式:

     

    输出到文件manager.out中。

    输出文件包括q行。

    输出文件的第i行输出1个整数,为第i步操作中改变安装状态的软件包数。

      这题有点像上面那道模板题。这题其实已经暗示我们很多了。首先,0号软件包不依赖任何软件包——这不就是说0为根节点吗?其次,依赖关系——这不就是让我们把u向着依赖它的v连一条边吗?于是我们就建好了一颗树。如果我们要安装软件包A,由题意得,我们需要将u到根节点路上所有为安装的软件包都安装上;而删除u呢?又由题意得,我们需要删掉所有依赖u的软件包,而依赖那些软件包的软件包也得被删掉。这不就是上一题写过的对子树的操作吗?所以我们只需要再用线段树维护一下区间上已安装的软件包个数,这个题就也被切掉了。

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #define maxn 100010
    #define maxm 100010
    using namespace std;
    
    struct edge{
        int to, next;
        edge(){}
        edge(const int &_to, const int &_next){
            to = _to;
            next = _next;
        }
    }e[maxn << 1];
    int head[maxn], k;
    
    struct node{
        int l, r, c, f;
    }t[maxn << 2];
    
    int size[maxn], fa[maxn], dep[maxn], son[maxn];
    int dfn[maxn], id[maxn], top[maxn], cnt[maxn], tot;
    int n, m;
    
    inline void add(const int &u, const int &v){
        e[k] = edge(v, head[u]);
        head[u] = k++;
    }
    
    void dfs_getson(int u){
        size[u] = 1;
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to;
            if(v == fa[u]) continue;
            fa[v] = u, dep[v] = dep[u] + 1;
            dfs_getson(v);
            size[u] += size[v];
            if(size[v] > size[son[u]]) son[u] = v;
        }
    }
    
    inline void dfs_rewrite(int u, int tp){
        top[u] = tp, dfn[u] = ++tot, id[tot] = u;
        if(son[u]) dfs_rewrite(son[u], tp);
        for(int i = head[u]; ~i; i = e[i].next){
            int v = e[i].to;
            if(v != fa[u] && v != son[u]) dfs_rewrite(v, v);
        }
        cnt[u] = tot;
    }
    
    void build(int d, int l, int r){
        t[d].l = l, t[d].r = r;
        if(l == r) return;
        int mid = l + r >> 1;
        build(d << 1, l, mid), build(d << 1 | 1, mid + 1, r);
    }
    
    inline void down(int d){
        if(t[d].f == 2){
            t[d << 1].c = t[d << 1].r - t[d << 1].l + 1;
            t[d << 1 | 1].c = t[d << 1 | 1].r - t[d << 1 | 1].l + 1;
            t[d << 1].f = t[d << 1 | 1].f = t[d].f;
        }else if(t[d].f == 1){
            t[d << 1].c = t[d << 1 | 1].c = 0;
            t[d << 1].f = t[d << 1 | 1].f = t[d].f;
        }
        t[d].f = 0;
    }
    
    int change(int d, const int &l, const int &r, const int &op){
        if(l <= t[d].l && t[d].r <= r){
            int ans = t[d].c;
            if(op == 2) t[d].c = t[d].r - t[d].l + 1;
            else t[d].c = 0;
            t[d].f = op;
            return ans;
        }
        if(op) down(d);
        int mid = t[d].l + t[d].r >> 1, ans = 0;
        if(l <= mid) ans += change(d << 1, l, r, op);
        if(r > mid) ans += change(d << 1 | 1, l, r, op);
        t[d].c = t[d << 1].c + t[d << 1 | 1].c;
        return ans;
    }
    
    inline void change_path();
    inline void change_sontree();
    
    int main(){
        memset(head, -1, sizeof head);
        scanf("%d", &n);
        for(int i = 2; i <= n; i++){
            int v;
            scanf("%d", &v);v++;
            add(i, v), add(v, i);
        }
        dfs_getson(1);
        dfs_rewrite(1, 1);
        build(1, 1, tot);
        
        scanf("%d", &m);
        while(m--){
            string op;
            cin >> op;
            if(op == "install") change_path();
            else change_sontree();
        }
        return 0;
    }
    
    inline void change_path(){
        int u, ans;
        scanf("%d", &u);u++;
        ans = dep[u] - dep[1] + 1;
        while(top[u] != 1){
            ans -= change(1, dfn[top[u]], dfn[u], 2);//被删掉的个数就等于节点总数减被安装了的软件包个数
            u = fa[top[u]];
        }
        ans -= change(1, 1, dfn[u], 2);
        printf("%d\n", ans);
    }
    
    inline void change_sontree(){
        int u, ans;
        scanf("%d", &u);u++;
        ans = change(1, dfn[u], cnt[u], 1);
        printf("%d\n", ans);
    }

      这里的节点编号要加1。注意这不是习惯!为什么呢?首先,我们的son数组一开始都是0,若不给节点编号加1的话,第二次DFS时就可能出错。


     

    P2486 [SDOI2011]染色

      这是一道很好的树剖题(至少不是模板)。很直接地,我们会想到用线段树记下区间内的颜色段的数量。于是我们递归下去,如果到了所要改的区间,我们就把区间的颜色段数量改成1就好了。但回溯时,若左儿子的右端点颜色和右儿子的左端点颜色一样,怎么判断呢?于是我们需要再记下两个信息:区间左端点的颜色和右端点的颜色。若左儿子的右端点颜色和右儿子的左端点颜色一样,将两个儿子的颜色段数加起来后再减1即

    可。就是代码有点难调,我的那个BUG代码还没调好(果然太弱了)。


    P2590 [ZJOI2008]树的统计

    题目描述

    一棵树上有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”的形式给出。

    输出格式:

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

      真正的模板题。如果你觉得你写树剖还不熟练,可以拿这题练(shui)练(jing)手(yan)。话说树剖的代码真的难调。


    P4114 Qtree1

    题目描述

    给定一棵n个节点的树,有两个操作:

    • CHANGE i ti 把第i条边的边权变成ti

    • QUERY a b 输出从a到b的路径中最大的边权,当a=b的时候,输出0

    输入输出格式

    输入格式:

    第一行输入一个n,表示节点个数

    第二行到第n行每行输入三个数,ui,vi,wi,分别表示 ui,vi有一条边,边权是wi

    第n+1行开始,一共有不定数量行,每一行分别有以下三种可能

    CHANGE,QUERY同题意所述

    DONE表示输入结束

    输出格式:

    对于每个QUERY操作,输出一个数,表示a b之间边权最大值

     

      这道题的技巧在很多树剖题都会用到~我们树剖时,计算的都是点权对不对?可是这题就不同些,给的是边权。这时怎么办呢?就用到了一种技巧,叫.......我也不知道叫什么。就是把边权转化为点权。怎么转呢?假如有边(u,v),如果我们把边权存在深度大的那个节点上去,也就是在节点x存下x连向父亲节点的边的权值。这样有什么用呢?想想,除了根节点,每个节点都唯一地只有一个父亲对吧,所以这样存不就把n-1条边的权值存在n-1个点上了吗?而那个没存的就是根节点了。于是,计算边权的题就可以转化为计算点权的题了。不过这样做还需要注意一个事项,由于每个点存的都是连向父亲边的边权,所以我们在计算树上两点之间的信息时,这两点的lca是不可用的(我不会告诉你我因为这个写爆过)



     

      例题就讲到这里吧。。。

      其实树剖还可以做lca。现有树上两点u,v,若求他们的lca,就树剖后一直跳链,直到top相同为止。此时深度小的那个就是lca了~也就是说现在我们有三种求lca的方法了:树上倍增、Tarjan和树剖(还有向上标记)。我们来对比一下。其实三种算法的思路都是一样,一直往上跳即可。而树上倍增时跳的是2的k次方,虽然很大,但还是没有树剖跳一跳链跳得彻底。而树剖跳的时候,如果链多了,还是会费时的。但Tarjan就异常强大了,在遍历图的过程中遇到了可以回答的询问就能得出答案,你可以理解为现在遍历到了u,而询问里有求lca(u,v)并且v已经遍历过,此时lca就是v在并查集的生成树里的祖先,也就是直接把u,v直接拽到了lca的位置去,跳都不跳了。但毕竟是离线算法,费空间......再对比一下时间复杂度,树上倍增为O((N+M)logN),树剖为(N+MlogN),Tarjan为O(N+M),Tarjan最优。而空间复杂度呢?树上倍增法为O(NlogN),树剖为O(N),Tarjan为O(N+M)(询问与并查集),树剖最优。综上,个人认为树剖还是最好的求lca的算法(虽然有点小题大做并且暴力得一批)。所以你们可以尝试做一下lca的题:

    P3379 【模板】最近公共祖先(LCA)

    转载于:https://www.cnblogs.com/akura/p/10692600.html

    展开全文
  • 整篇文章都在解释什么是哈夫曼树,怎么用,用于什么,怎么构建,然后就给出频率,让出整棵(最优二叉树)哈夫曼树的权值。 【思路】 首先给出一个博客地址,能够清楚的了解什么是哈夫曼树:...

    题目来源:https://cn.vjudge.net/problem/ZOJ-2339
    【题意】
    整篇文章都在解释什么是哈夫曼树,怎么用,用于什么,怎么构建,然后就给出频率,让算出整棵(最优二叉树)哈夫曼树的权值。
    【思路】
    首先给出一个博客地址,能够清楚的了解什么是哈夫曼树:http://www.cnblogs.com/wuyuankun/p/3982216.html
    然后就可以把这道题A了。
    【代码】

    #include<map>
    #include<stack>
    #include<queue>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<string>
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef long long LL;
    const int INF=0x3f3f3f3f;
    int main()
    {
        int t;
        scanf("%d",&t);
        priority_queue<LL,vector<LL>,greater<LL> > q;
        while(t--)
        {
            int n,s;
            while(!q.empty())
                q.pop();
            scanf("%d",&n);
            while(n--)
            {
                scanf("%d",&s);
                q.push(s);
            }
            LL ans=0,x,y;
            while(!q.empty())
            {
                x=q.top();
                q.pop();
                if(q.empty())
                break;
                y=q.top();
                q.pop();
                ans+=x+y;
                q.push(x+y);
            }
            printf("%lld\n",ans);
            if(t!=0)
                printf("\n");
        }
    }
    
    展开全文
  • 那么这条边最多可以被使用\(min(x,y)*2\)次(因为有进有出),即贡献最大为\(min(x,y)*2*\)这条边的权值。 那么能不能让每一条边的被使用达到最大呢? 显然可以。 那怎么快速这个东西呢?不可能每加一个点就dfs一...

    乍一看我不会。
    先不考虑加点。
    先考虑没有那个除\(2\)
    考虑每一条边的贡献,假设某一条边把这棵树分成大小为x,y的两个部分。
    那么这条边最多可以被使用\(min(x,y)*2\)次(因为有进有出),即贡献最大为\(min(x,y)*2*\)这条边的权值。
    那么能不能让每一条边的被使用达到最大呢?
    显然可以。
    那怎么快速算这个东西呢?不可能每加一个点就dfs一遍吧。那样就\(T\)飞了。
    实际上这个东西就是每个点到树的重心的距离\(*2\)
    为什么?因为满足以树的重心为根每一个子树大小\(<\)总共的节点数。每一棵子树内所有点都要向子树外也就是根(重心)连边。
    然后发现这个除\(2\)没有向下取整。
    所以就是求所有的点到重心的距离和。
    然后加点的话可以离线然后\(dfn序\)维护一下。

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define ls now<<1
    #define rs now<<1|1
    const int N=101000;
    int cnt,head[N];
    struct edge{
        int to,nxt;
    }e[N*2];
    void add_edge(int u,int v){
        cnt++;
        e[cnt].nxt=head[u];
        e[cnt].to=v;
        head[u]=cnt;
    }
    int size[N],fa[N][22],dep[N],dfn[N],tot;
    void dfs(int u,int f){
        size[u]=1;
        dfn[u]=++tot;
        fa[u][0]=f;dep[u]=dep[f]+1;
        for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
        int maxson=-1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(v==f)continue;
            dfs(v,u);
            size[u]+=size[v];
        }
    }
    int getlca(int x,int y){
        if(dep[x]<dep[y])swap(x,y);
        for(int i=20;i>=0;i--)
            if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
        if(x==y)return x;
        for(int i=20;i>=0;i--)
            if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    int sum[N*4];
    void update(int now){
        sum[now]=sum[ls]+sum[rs];
    }
    void build(int l,int r,int now){
        if(l==r){
            if(l==1)sum[l]=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
        update(now);
    }
    void add(int l,int r,int x,int now){
        if(l==r){
            sum[now]=1;
            return;
        }
        int mid=(l+r)>>1;
        if(x>mid)add(mid+1,r,x,rs);
        else add(l,mid,x,ls);
        update(now);
    }
    int check(int l,int r,int L,int R,int now){
        if(l==L&&r==R)return sum[now];
        int mid=(l+r)>>1;
        if(L>mid)return check(mid+1,r,L,R,rs);
        else if(R<=mid)return check(l,mid,L,R,ls);
        else return check(l,mid,L,mid,ls)+check(mid+1,r,mid+1,R,rs);
    }
    int up(int x,int y){
        for(int i=20;i>=0;i--)
            if(dep[fa[x][i]]>dep[y])x=fa[x][i];
        return x;
    }
    int read(){
        int sum=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
        return sum*f;
    }
    int n,root;
    long long ans;
    int main(){
        n=read();n++;
        root=1;ans=0;
        for(int i=2;i<=n;i++){
            int v=read();
            add_edge(i,v);add_edge(v,i);
        }
        dfs(1,0);
        build(1,n,1);
        for(int i=2;i<=n;i++){
            add(1,n,dfn[i],1);
            int lca=getlca(root,i);
            ans+=(long long)(dep[root]+dep[i]-2ll*dep[lca]);
            if(lca==root){
                int x=up(i,root);
                int sizex=check(1,n,dfn[x],dfn[x]+size[x]-1,1);
                if(sizex>i-sizex)root=x,ans+=(long long)(i-sizex*2ll);
            }
            else{
                int x=fa[root][0];
                int sizex=check(1,n,dfn[root],dfn[root]+size[root]-1,1);
                if(i-sizex>sizex)root=x,ans+=(long long)(sizex*2ll-i);
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/Xu-daxia/p/10479699.html

    展开全文
  • 给定一棵,查询路径第k大值,带修改。 就是bzoj2588+bzoj3196 上建主席。然后对于修改,修改点x的权值,只...树状数组套动态加点线段内存究竟怎么算.jpg???能开多大是多大好了,反正是要比logn^2小很多?这样
  • 实际上我们可以发现一个某一个子树的权值在某一个区间的话,对于另外一个子树中答案对根的影响是一个区间的。所以可以直接打区间乘法标记。 对,然后就想到了动态开点线段树。 现在考虑具体怎么在合并两个儿子的时候...
  • 最小生成

    2018-11-20 21:08:11
    最小生成怎么用最短路径把图所有结点给连起来。 这里有两种方式,一种是Kruskal方法,简称K方法,另一种是Prim方法,简称P方法。 K方法:是根据最小权重边来算的,通过一个优先级队列来存放所有边,...
  • 文章目录一个问题前言与可持久化线段...虽然主席树的名字是乱起的,但是它是“基于权值线段树的可持久化线段树”,而并不是纯粹的可持久化线段树。主席树可以解决的问题都是关于求可持久化的排名(和平衡树有些相似),
  • 首先暴力\(n^2\)是很好想,就是把当前节点概率按照权值大小做前缀和和后缀和然后对于每一个值直接在另一个子里面出贡献和就可以了,注意乘上选最大概率是小于当前权值的部分,选最小是大于当前权值的部分 ...
  • #define INFINTY 51//不知道怎么定义,才无穷大 #define MAX_VERTEX_NUM 50 typedef struct { int a[MAX_VERTEX_NUM];//顶点向量 int edges[MAX_VERTEX_NUM[MAX_VERTEX_NUM];//邻接矩阵 int n,;//顶点数 }...
  • [APIO2018] Duathlon 铁人两项 LG传送门 圆方树+简单DP。...换句话说就是简单路径,用(广义)圆方树的基本条件已经满足,可以把问题变到树上:令方点的权值为所在点双的大小,圆点会被重所以点权为\(-1\)...
  • CF547E 二分+sa+主席

    2020-06-05 09:14:26
    这提供一个sa+主席树的做法,这个用做法就你顺势可以在敲掉基本一样的洛谷P4084 题意询问的是k串在[L,R]的串里面出现了多少次,不同位置多次。 对于一个串在SA里的位置以及和他最像的位置必然是连续的(字典序的...
  • 一棵有边权的树,问有多少对点简单路径权值和模3为0 思路: 简单的树分治,每次处理出重心后,处理出到重心距离,然后为0直接平方,1和2相乘并乘2(因为(2,3),(3,2)两对),然后删去不合法...
  • 给一个 n 个点 m条边的联通图(分黑白两种点),每条边的权值 为 2 ^ k, k 为依次给出边的序号,求所有所有黑点到白点的距离和的最小值。 思路: 一开始看上去还以为是最短路,但连边权都存不下来,又有这么多点要...
  • 扶额 这么一n^3空间是可以啊……怎么会MLE…… 好吧 改成二维 用三维写题解 好理解 dp[i][j][0][cnt] : i子树走j步回到i用前cnt个分组(son)最大权值 dp[i][j][1][cnt] : i子树走j步不回到i用前cnt...
  • 大意:n个点m条边,问如果每个联通分支中最多有一个环,最后可以组成的最大的权值和是多少。思路:类似一颗生成,是的话那么一定是最大生成。那么怎么判断是不是会有环的形成呢?那么就可以用并查集判断了,所以...
  • 求动态逆序对,BIT套权值线段即可。 空间和时间都是O((n+m)log2n)O((n+m)log2n)O((n+m)log^2n) 最近怎么老是错空间qaq #include &lt;bits/stdc++.h&gt; using namespace std; #define ll long long...
  •  区间合并线段树的题,第一次写,对于一颗子树,无论这个子树怎么交换,都不会对其他子树的逆序对造成影响,所以就直接逆序对就好。  注意叶子节点是1到n的全排列,所以每个权值都只会出现1次,合并很好写。 ...
  • BZOJ 2631: tree|动态

    2016-02-25 08:08:57
    就是将乘法和加法合并起来做一个标记,mulmul数组和plusplus数组两个数组做一个标记,设权值为xx那么标记意思就是把所有子节点的的xx都变为:mul∗x+plusmul*x+plus这样只要多维护一个sizesize数组就可以维护...
  • 然后题意就是,在一个平面直角坐标系上,有一些点,每个点有一个权值,用一个矩形框去框住他们,问怎么才能使框住的所有点的权值和最大,边界上的点不算。 边界上的点 不算,我之前只做到过一次边界上的点的啊,...
  • 嘛,就是把一组权值相等边分成一组,然后对于每个连通块暴力一下生成个数,然后用并查集做一下暴力缩点就好了,乘法原理即可,注意不能写路径压缩……手贱打了一个结果连样例都过不了去掉后就A了...
  • 给你一个字符串,每个位置有一个权值(可正可负),对于每一个i∈[0,n−1]i\in[0,n-1]i∈[0,n−1],求所有lcp长度为iii后缀对数,并且求每一对lcp为iii后缀两个权值相乘最大值。长度为iiilcp也可以做...
  • CF1010F Tree

    2019-02-28 20:16:00
    真·毒瘤题 这个题面写错了一句话。...且这棵树的权值和为x。 那么就可以插板法一下了,因此它与树的结构无关,只与大小有关。 因此我们只需要对第一种操作一下联通块大小为k的方案数即可。 直接dp是n^2...
  • 题意:给一棵树,每条边有权....开一个t[i]表示整棵树中权值和为i的路径有多少条,那么我们分治每一颗树的时候,再出子节点到当前根的dis[x]权值距离和d[x]点数距离,然后就可以直接更新了ans=min(ans,t[k-dis[x]]+d
  • 一个根节点的权值会决定一棵全部的权值是显然的(一开始也想,枚举一下??呵呵,这么sb的做法怎么可能对,然后就想各种各样的乱搞) 在扒到题解之后,发现还还有取log这个奇巧淫技,, 那么这样对每个点一下...
  • 运气不错,刚好碰到了会做的题目 ...结果发现不是求到父亲的链的贡献,而是求子树的贡献,又有权值线段树,不好求。 干脆直接合并起来了。 赛后消化 T2搜索+背包+计数即可,看似是数位DP,实际...
  • 那么这是个WC原题,dfs一遍找到所有有用的环丢进线性基即可,因为每一个环的权值都是可以取到且不对其他部分产生影响的。  现在给了一棵,不妨就把他看做原图的dfs。每增加一条边就是增加了一个环。出权值后...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

树的权值怎么算