精华内容
下载资源
问答
  • Qtree

    2017-02-14 22:14:00
    Qtree Ⅰ 题意:https://vjudge.net/problem/SPOJ-QTREE  带修路径查询最大边权 sol :树链剖分,之后每条重链就是一个连续的区间,拿线段树维护即可  简单讲讲链剖吧.....就是把树边划分为轻重边,重边的定义...

    Qtree Ⅰ

    题意:https://vjudge.net/problem/SPOJ-QTREE

       带修路径查询最大边权

    sol :树链剖分,之后每条重链就是一个连续的区间,拿线段树维护即可

        简单讲讲链剖吧.....就是把树边划分为轻重边,重边的定义是和siz最大的儿子之间的边

        通过两次dfs实现,可以证明重链(重边形成的链)不超过logn条

        直接上代码吧,复杂度O(nlogn^2)

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int Mx=10010;
    struct Edge { int x,y,val; } edge[Mx];
    struct Tree { int l,r,val; } tree[4*Mx];
    int n,cnt,dep[Mx],siz[Mx],fa[Mx],num[Mx],son[Mx],top[Mx];//top表示最近的重链父节点 
    int tot,nxt[2*Mx],head[Mx],ver[2*Mx],val[2*Mx];
    void clear()
    {
        memset(head,0,sizeof(head));
        memset(son,0,sizeof(son));
        cnt=0;tot=0;
    }
    inline void add(int x,int y,int z)
    {
        tot++;
        nxt[tot]=head[x];
        ver[tot]=y;
        val[tot]=z;
        head[x]=tot;    
    }
    //链剖 
    void dfs1(int u,int Fa,int Dep)
    {
        dep[u]=Dep,siz[u]=1,son[u]=0,fa[u]=Fa;
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i];
            if(v==Fa) continue;
            dfs1(v,u,Dep+1);
            siz[u]+=siz[v];
            if(siz[son[u]]<siz[v]) son[u]=v;
        }
    }
    void dfs2(int u,int Top)
    {
        top[u]=Top,num[u]=++cnt;
        if(son[u]) dfs2(son[u],Top);
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i];
            if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
        }
    }
    //线段树 
    void pushup(int x) { tree[x].val=max(tree[x<<1].val,tree[x<<1|1].val); }
    void build(int l,int r,int v)
    {
        tree[v].l=l;tree[v].r=r;
        if(l==r) { tree[v].val=val[l]; return ; }
        int mid=(l+r)>>1;
        build(l,mid,v*2); build(mid+1,r,v*2+1);
        pushup(v);
    }
    void update(int u,int v,int val)
    {
        if(tree[u].l==tree[u].r) { tree[u].val=val; return ; }
        int mid=(tree[u].l+tree[u].r)/2;
        if(v<=mid) update(u*2,v,val);
        else update(u*2+1,v,val);
        pushup(u);
    }
    int query(int x,int l, int r)
    {
        if(tree[x].l>=l&&tree[x].r<=r) return tree[x].val;
        int ans=0,mid=(tree[x].l+tree[x].r)/2;
        if(l<=mid) ans=max(ans,query(x<<1,l,r));
        if(r>mid) ans=max(ans,query(x<<1|1,l,r));
        return ans;
    }
    int solve(int u,int v)
    {
        int ans=0,Top1=top[u],Top2=top[v];
        while(Top1!=Top2)
        {
            if(dep[Top1]<dep[Top2]) swap(Top1,Top2),swap(u,v);
            ans=max(ans,query(1,num[Top1],num[u]));
            u=fa[Top1];Top1=top[u];
        }
        if(u==v) return ans;
        if(dep[u]>dep[v]) swap(u,v);
        ans=max(ans,query(1,num[son[u]],num[v]));
        return ans;
    }
    int main()
    {
        int T;scanf("%d",&T);
        while(T--)
        {
            clear();
            scanf("%d",&n);
            for(int i=1,x,y,z;i<n;i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                edge[i].x=x;edge[i].y=y;edge[i].val=z;
                add(x,y,z);add(y,x,z);
            }
            dfs1(1,0,1);dfs2(1,1);
            for(int i=1;i<n;i++)
            {
                if(dep[edge[i].x]<dep[edge[i].y]) swap(edge[i].x,edge[i].y);
                val[num[edge[i].x]]=edge[i].val;
            }
            build(1,cnt,1);
            while(1)
            {
                char s[200];scanf("%s",s);if(s[0]=='D') break;
                int x,y; scanf("%d%d",&x,&y);
                if(s[0]=='Q') printf("%d\n",solve(x,y));
                if (s[0]=='C') update(1,num[edge[x].x],y);
            }
        }
        return 0;
    }

     

    Qtree Ⅱ

    题意:https://vjudge.net/problem/SPOJ-QTREE2

       路径查询距离、第K个点

    sol :本来想都没想直接写了个链剖,结果发现不用QAQ

       这应该是Qtree1~7里最水的吧QAQ,直接倍增就行了

       预处理每个点到根的路径长度,第一问求出lca后直接输出dis[x]+dis[y]-2dis[lca]即可

       第二问需要考虑是在x-lca的路径上还是y-lca的路径上,然后直接倍增求第k个祖先即可

       P.S.这里可以扩展一下,广义的树上倍增,orz集训队dalao

         可以有O(D * N ^ ((D+1)/D))的时间的预处理。
         设K=N^(1/D),预处理出所有点分别的第i*K^j个祖先(对于所有1<=i<K且0<=j<D)。
         然后每次求时将要跳的步数转化成一个不超过D位的K进制数就可以在O(D)的时间内求出来啦。
         我们平时在说的倍增(预处理出每个点的第1,2,4,8,16,...个祖先)是D=log2(N),K=2的特例。
         D的值可以根据需要调整。

        话说,我一开始还wa了半天,结果发现是return 0打到了while(T--)里面QAQ

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int Mx=10010;
    int n,len,tmp,fa[Mx],fa1[Mx][30],dep[Mx],val[Mx];
    int tot,head[Mx],nxt[2*Mx],ver[2*Mx],val1[2*Mx];
    void clear()
    {
        tot=0;
        memset(head,0,sizeof(head));
        memset(val,0,sizeof(val));
        memset(fa1,0,sizeof(fa1));
    }
    inline void add(int x,int y,int z)
    {
        tot++;
        nxt[tot]=head[x];
        ver[tot]=y;
        val1[tot]=z;
        head[x]=tot;
    }
    void dfs(int u,int Fa,int Val,int Dep)
    {
        dep[u]=Dep,fa[u]=Fa,val[u]=val[Fa]+Val;
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i];
            if(v==Fa) continue;
            dfs(v,u,val1[i],Dep+1);
        }
    }
    void pre()
    {
        for(int i=1;i<=n;i++) fa1[i][0]=fa[i];
        for(int j=1;1<<j<=n;j++)
            for(int i=1;i<=n;i++)
                fa1[i][j]=fa1[fa1[i][j-1]][j-1];
    }
    int find_lca(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        for(tmp=0,len=0;(1<<tmp)<=dep[x];tmp++); tmp-=1;
        for(int j=tmp;j>=0;j--)
            if(dep[x]-(1<<j)>=dep[y]) x=fa1[x][j];
        if(x==y) return x;
        for(int j=tmp;j>=0;j--)
            if(fa1[x][j]!=-1&&fa1[x][j]!=fa1[y][j])
                x=fa1[x][j],y=fa1[y][j];
        return fa1[x][0];
    }
    int find_fa(int x,int k)
    {
        int Dep=dep[x]-k+1;
        for(tmp=0;(1<<tmp)<=dep[x];tmp++); tmp--;
        for(int j=tmp;j>=0;j--)
        {
            if(dep[x]==Dep) break;
            if(dep[fa1[x][j]]>=Dep) x=fa1[x][j];
        }
        return x;
    }
    int main()
    {
        int T;scanf("%d",&T);
        while(T--)
        {
            clear(); scanf("%d",&n);
            for(int i=1,x,y,z;i<n;i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);add(y,x,z);
            }
            fa[1]=1;dfs(1,1,0,1);pre();
            while(1)
            {
                char ch[30];scanf("%s",ch);
                if(ch[1]=='O') break;
                if(ch[0]=='D')
                {
                    int x,y,lca; scanf("%d%d",&x,&y);
                    lca=find_lca(x,y);
                    printf("%d\n",val[x]+val[y]-(2*val[lca]));
                }
                else
                {
                    int x,y,k,lca;scanf("%d%d%d",&x,&y,&k);
                    lca=find_lca(x,y);
                    if(dep[x]-dep[lca]+1>k) printf("%d\n",find_fa(x,k));
                    else printf("%d\n",find_fa(y,dep[y]+dep[x]-(2*dep[lca])+2-k));
                }
            }
        }
        return 0;
    }

     

    Qtree Ⅲ

    题意:https://vjudge.net/problem/CodeChef-QTREE

       给一棵树,黑白染色,有两个操作:单点颜色修改、查询1~v的路径上最先出现黑点的位置

    sol :显然LCT可做

     

    转载于:https://www.cnblogs.com/xiaoxubi/p/6399449.html

    展开全文
  • QTree

    2017-02-10 09:35:00
    1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <queue> 5 #include <algorithm> 6 #include <cstring>... 7 #include &l...
      1 #include <cstdio>
      2 #include <iostream>
      3 #include <cmath>
      4 #include <queue>
      5 #include <algorithm>
      6 #include <cstring>
      7 #include <climits>
      8 #define MAXN 20000+10
      9 using namespace std;
     10 int n,m,q,num,head[MAXN],t;
     11 int v[MAXN],fa[MAXN][100],g[MAXN][100];
     12 int deep[MAXN];
     13 struct Edge{
     14     int next,dis,to,from;
     15 }edge[MAXN<<1];
     16 void add(int from,int to,int dis)
     17 {
     18     edge[++num].next=head[from];
     19     edge[num].to=to;
     20     edge[num].from=from;
     21     edge[num].dis=dis;
     22     head[from]=num;
     23 }
     24 void dfs(int x)
     25 {
     26     for(int i=head[x];i;i=edge[i].next)
     27     if(!deep[edge[i].to])
     28     {
     29         deep[edge[i].to]=deep[x]+1;
     30         g[edge[i].to][0]=edge[i].dis;
     31         fa[edge[i].to][0]=x;
     32         dfs(edge[i].to);
     33     }
     34 }
     35 void init()
     36 {
     37     deep[1]=1;
     38     dfs(1);
     39     for(int j=1;(1<<j)<=n;j++)
     40         for(int i=1;i<=n;i++)
     41         if(fa[i][j-1])    
     42             fa[i][j]=fa[fa[i][j-1]][j-1],
     43             g[i][j]=g[i][j-1]+g[fa[i][j-1]][j-1];
     44 }
     45 int query(int k,int from,int to)
     46 {
     47     int a=from,b=to;
     48     if(deep[a]>deep[b]) swap(a,b);
     49     int d=deep[b]-deep[a],ans=0,lca=0;
     50     for(int i=0;(1<<i)<=d;i++)
     51         if((1<<i)&d) ans+=g[b][i],b=fa[b][i];
     52     if(a==b) lca=a;
     53     else
     54     {
     55         for(int j=30;j>=0;j--)
     56         if(fa[a][j]!=fa[b][j])
     57         {
     58             ans+=g[a][j]+g[b][j];
     59             a=fa[a][j];b=fa[b][j];
     60         }
     61         ans+=g[a][0]+g[b][0];lca=fa[a][0];
     62     }
     63     
     64     if(k==-1) return ans;
     65     int df=deep[from]-deep[lca]+1,dt=deep[to]-deep[lca]+1,p=0;
     66     if(k==df) return lca;
     67     if(k<df)
     68     {
     69         p=from,k=k-1;
     70     }
     71     else
     72     {
     73         p=to,k=(df+dt-1)-k;
     74     }
     75     for(int j=0;(1<<j)<=k;j++)
     76             if((1<<j)&k) p=fa[p][j];
     77     return p;
     78 }
     79 int main()
     80 {
     81     freopen("i.in","r",stdin);
     82     freopen("i.out","w",stdout);
     83     scanf("%d",&t);
     84     for(int l=1;l<=t;l++)
     85     {
     86         num=0;
     87         memset(edge,0,sizeof(edge));
     88         memset(head,0,sizeof(head));
     89         memset(fa,0,sizeof(fa));
     90         memset(g,0,sizeof(g));
     91         memset(deep,0,sizeof(deep));
     92         scanf("%d",&n);
     93         int x,y,z;
     94         for(int i=1;i<n;i++)
     95         {
     96             scanf("%d%d%d",&x,&y,&z);
     97             add(x,y,z);
     98             add(y,x,z);
     99         }
    100         init();
    101         char c[10];
    102         while(scanf("%s",c)&&(!(c[0]=='D'&&c[1]=='O')))
    103         {
    104             if(c[0]=='D')
    105             {
    106                 scanf("%d%d",&x,&y);
    107                 printf("%d\n",query(-1,x,y));
    108             }else
    109             if(c[0]=='K')
    110             {
    111                 scanf("%d%d%d",&x,&y,&z);
    112                 printf("%d\n",query(z,x,y));
    113             }
    114         }
    115         printf("\n");
    116     }
    117     return 0;
    118 }

     

    转载于:https://www.cnblogs.com/yangyaojia/p/6385008.html

    展开全文
  • QTREE4

    2018-11-26 23:20:00
    QTREE4 点分治  题目链接:https://www.luogu.org/problemnew/show/P4115  参考:http://www.cnblogs.com/yanshannan/p/9411098.html     首先观察此题每条边的长度-1000<=w<=1000  而当0<=w...

    QTREE4

    点分治

      题目链接:https://www.luogu.org/problemnew/show/P4115

      参考:http://www.cnblogs.com/yanshannan/p/9411098.html 

      

        首先观察此题每条边的长度-1000<=w<=1000

        而当0<=w<=1000的时候会有一个更优的nlogn解法

          线段树维护树的直径

          怎么维护?

          有一个结论:

            一颗树内,某些点构成的点集 形成的一个新树,该树的直径端点为x,y;

            现在新加入一个点z,形成新的点集构成的新树的直径端点为(x,y)或(x,z)或(y,z);

          于是用线段树维护一下就好,合并时用线段树两个儿子代表的树直径端点更新即可

       lca用dfs序+st表,单次查询O1

    线段树维护的代码

      1 #include<iostream>
      2 #include<cstdio>
      3 using namespace std;
      4 const int M=100009;
      5 int n,m,num=0,id=0,sum;
      6 int head[M],fir[M],L[M<<1],pw[23],val[M],f[M<<1][23],dep[M];
      7 struct P{int to,ne,w;}e[M<<1];
      8 int ls[M<<2],rs[M<<2],len[M<<2];
      9 bool vis[M];
     10 int read(){
     11     int rex=0,f=1;char ch=getchar();
     12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
     13     while(ch>='0'&&ch<='9'){rex=rex*10+ch-'0';ch=getchar();}
     14     return rex*f;
     15 }
     16 void dfs(int u,int fa,int w){
     17     f[fir[u]=++id][0]=u;val[u]=w;dep[u]=dep[fa]+1;
     18     for(int i=head[u];i;i=e[i].ne){
     19         int v=e[i].to;
     20         if(v!=fa){dfs(v,u,w+e[i].w);f[++id][0]=u;}
     21     }
     22 }
     23 int Min(int x,int y){
     24     return dep[x]<dep[y]?x:y;
     25 }
     26 int ask(int l,int r){
     27     l=fir[l],r=fir[r];
     28     if(l>r)swap(l,r);
     29     int k=L[r-l+1];
     30     return Min(f[l][k],f[r-pw[k]+1][k]);
     31 }
     32 int dis(int u,int v){
     33     return val[u]+val[v]-2*val[ask(u,v)];
     34 }
     35 void merge(int a,int b,int c,int dist=0){
     36     if(ls[a]==0||ls[b]==0){
     37         ls[c]=ls[a]+ls[b];
     38         rs[c]=rs[a]+rs[b];
     39         len[c]=len[a]+len[b];
     40         return;
     41     }
     42     if(len[a]<len[b])swap(a,b);
     43     ls[c]=ls[a],rs[c]=rs[a],len[c]=len[a];
     44     dist=dis(ls[a],ls[b]);
     45     if(dist>len[c]){len[c]=dist;ls[c]=ls[a];rs[c]=ls[b];}
     46     dist=dis(ls[a],rs[b]);
     47     if(dist>len[c]){len[c]=dist;ls[c]=ls[a];rs[c]=rs[b];}
     48     dist=dis(rs[a],ls[b]);
     49     if(dist>len[c]){len[c]=dist;ls[c]=rs[a];rs[c]=ls[b];}
     50     dist=dis(rs[a],rs[b]);
     51     if(dist>len[c]){len[c]=dist;ls[c]=rs[a];rs[c]=rs[b];}
     52 }
     53 void build(int now,int l,int r){
     54     if(l==r){
     55         ls[now]=rs[now]=l;
     56         len[now]=0;
     57         return;
     58     }
     59     int mid=(l+r)>>1;
     60     build(now<<1,l,mid);
     61     build(now<<1|1,mid+1,r);
     62     merge(now<<1,now<<1|1,now);
     63 }
     64 void update(int now,int l,int r,int x){
     65     if(l==r){
     66         if(vis[x])ls[now]=rs[now]=len[now]=0;
     67         else ls[now]=rs[now]=x,len[now]=0;
     68         return;
     69     }
     70     int mid=(l+r)>>1;
     71     if(x<=mid)update(now<<1,l,mid,x);
     72     else update(now<<1|1,mid+1,r,x);
     73     merge(now<<1,now<<1|1,now);
     74 }
     75 int main(){
     76     n=read();
     77     for(int i=1,u,v,w;i<n;++i){
     78         u=read(),v=read(),w=read();
     79         e[++num]=(P){v,head[u],w};head[u]=num;
     80         e[++num]=(P){u,head[v],w};head[v]=num;
     81     }
     82     dfs(1,0,0);pw[0]=1;L[1]=0;
     83     for(int i=1;i<=19;++i)pw[i]=pw[i-1]<<1;
     84     for(int i=2;i<=id;++i)L[i]=L[i>>1]+1;
     85     for(int j=1;j<=19;++j){
     86         for(int i=1;i+pw[j]-1<=id;++i){
     87             f[i][j]=Min(f[i][j-1],f[i+pw[j-1]][j-1]);
     88         }
     89     }
     90     build(1,1,n);
     91     m=read();sum=n;
     92     for(int i=1;i<=m;++i){
     93         char c[5];
     94         scanf("%s",c);
     95         if(c[0]=='C'){
     96             int x=read();
     97             vis[x]^=1;
     98             update(1,1,n,x);
     99             if(vis[x])sum--;
    100             else sum++;
    101         }
    102         else {
    103             if(sum==0)printf("They have disappeared.\n");
    104             else printf("%d\n",len[1]);
    105         }
    106     }
    107     return 0;
    108 }
    View Code

     

        当然此题的w是可以<0的,所以树直径的结论就不满足了

        此时我们就需要用到另外一种算法:动态点分治(O(n log ^2 n))

        就是对分治树上的每个点开2个堆

          1:此子树白点到他父节点的距离大根堆 a

          2:此节点的每个儿子子树中的白点到该节点的最大值组成的大根堆 b

          1用来更新2,此时经过某个重心u的 两个白点最大距离 可以为    b[u]大根堆的   最大值和次大值之和

        最后再总的维护一个答案堆 ans 即可

        更新答案就分治树上往上走,顺便更新下经过节点的堆和答案堆即可

        这三种堆需要满足一种操作,pop(x);

          可以开个结构题,里面2个堆,插入堆和删除堆

          取堆顶时,插入堆堆顶和删除堆堆顶相同时,2个堆同时pop(),如果不同就return 插入堆.top();

        代码

          

      1 #include<iostream>
      2 #include<cstdio>
      3 #include<queue>
      4 using namespace std;
      5 const int M=100009;
      6 int n,m,num=0,id=0,sum=0;
      7 int head[M];
      8 int pw[23],L[M<<1],fir[M],val[M],dep[M],f[M<<1][23];
      9 struct P{int to,ne,w;}e[M<<1];
     10 int minn,rt,size,siz[M],ft[M];
     11 bool vis[M],co[M];
     12 struct Queue{
     13     priority_queue<int>s,t;int sz;
     14     inline void push(int x){s.push(x);sz++;}
     15     inline void pop(int x){t.push(x);sz--;}
     16     inline int top(){
     17         if(sz==0)return -1e9;
     18         while(!t.empty()&&s.top()==t.top())s.pop(),t.pop();
     19         return s.top();
     20     }
     21     inline int len(){
     22         if(sz<2)return 0;
     23         int x=top();pop(x);
     24         int y=top();push(x);
     25         return max(0,x+y);
     26     }
     27     inline void del(int k,int x){k==0?push(x):pop(x);}
     28 }a[M],b[M],ans;
     29 inline int read(){
     30     int rex=0,f=1;char ch=getchar();
     31     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
     32     while(ch>='0'&&ch<='9'){rex=rex*10+ch-'0';ch=getchar();}
     33     return rex*f;
     34 }
     35 void dfs(int u,int fa,int w){
     36     f[fir[u]=++id][0]=u;val[u]=w;dep[u]=dep[fa]+1;
     37     for(int i=head[u];i;i=e[i].ne){
     38         int v=e[i].to;
     39         if(v!=fa){dfs(v,u,w+e[i].w);f[++id][0]=u;}
     40     }
     41 }
     42 inline int Min(int x,int y){
     43     return dep[x]<dep[y]?x:y;
     44 }
     45 inline int ask(int l,int r){
     46     l=fir[l],r=fir[r];
     47     if(l>r)swap(l,r);
     48     int k=L[r-l+1];
     49     return Min(f[l][k],f[r-pw[k]+1][k]);
     50 }
     51 inline int dis(int u,int v){
     52     return val[u]+val[v]-2*val[ask(u,v)];
     53 }
     54 void getrt(int u,int fa){
     55     int ma=0;siz[u]=1;
     56     for(int i=head[u];i;i=e[i].ne){
     57         int v=e[i].to;if(v==fa||vis[v])continue;
     58         getrt(v,u);siz[u]+=siz[v];ma=max(ma,siz[v]);
     59     }
     60     ma=max(ma,size-siz[u]);
     61     if(minn>ma){minn=ma,rt=u;}
     62 }
     63 void DFS(int u,int fa,int now){
     64     a[now].push(dis(ft[now],u));
     65     for(int i=head[u];i;i=e[i].ne){
     66         int v=e[i].to;
     67         if(v!=fa&&!vis[v])DFS(v,u,now);
     68     }
     69 }
     70 void work(int u){
     71     if(ft[u])DFS(u,0,u);vis[u]=1;b[u].push(0);
     72     for(int i=head[u];i;i=e[i].ne){
     73         int v=e[i].to;if(vis[v])continue;
     74         minn=1e9,size=siz[u];
     75         getrt(v,0);ft[rt]=u;
     76         int la=rt;
     77         work(rt);b[u].push(a[la].top());
     78     }
     79     ans.push(b[u].len());
     80 }
     81 inline void change(int u){
     82     ans.pop(b[u].len());
     83     b[u].del(co[u],0);
     84     ans.push(b[u].len());
     85     for(int i=u;ft[i];i=ft[i]){
     86         int x=a[i].top();
     87         a[i].del(co[u],dis(ft[i],u));
     88         int y=a[i].top();
     89         if(x==y)continue;
     90         ans.pop(b[ft[i]].len());
     91         b[ft[i]].pop(x);
     92         b[ft[i]].push(y);
     93         ans.push(b[ft[i]].len());
     94     }
     95 }
     96 int main(){
     97     n=read();
     98     for(int i=1,u,v,w;i<n;++i){
     99         u=read(),v=read(),w=read();
    100         e[++num]=(P){v,head[u],w};head[u]=num;
    101         e[++num]=(P){u,head[v],w};head[v]=num;
    102     }
    103     dfs(1,0,0);pw[0]=1;L[1]=0;
    104     for(int i=1;i<=19;++i)pw[i]=pw[i-1]<<1;
    105     for(int i=2;i<=id;++i)L[i]=L[i>>1]+1;
    106     for(int j=1;j<=19;++j){
    107         for(int i=1;i+pw[j]-1<=id;++i){
    108             f[i][j]=Min(f[i][j-1],f[i+pw[j-1]][j-1]);
    109         }
    110     }
    111     minn=1e9,size=n;
    112     getrt(1,0);
    113     work(rt);
    114     m=read();sum=n;
    115     for(int i=1;i<=m;++i){
    116         char c[5];
    117         scanf("%s",c);
    118         if(c[0]=='C'){
    119             int x=read();
    120             co[x]^=1;
    121             change(x);
    122             sum+=co[x]?-1:1;
    123         }
    124         else {
    125             sum==0?printf("They have disappeared.\n")
    126             :printf("%d\n",ans.top());
    127         }
    128     }
    129     return 0;
    130 }
    View Code

     

     

    转载于:https://www.cnblogs.com/intercept/p/10023788.html

    展开全文
  • 谷歌地球影像qtree文件解译源码,可以用于解析最新影像数据,这部分是关键算法代码,提供解析思路,了解qtree文件的组织方式
  • SPOJ QTREE

    2018-04-06 13:55:00
    QTREE /* 题目大意:维护一棵树,允许修改边权以及查询链上最大值 题解:我们将边权转为点权,标记在深度较深的点上,树链剖分后用线段树处理即可 */ #include <cstdio> #include <cstring> ...

    QTREE

    /*
        题目大意:维护一棵树,允许修改边权以及查询链上最大值
        题解:我们将边权转为点权,标记在深度较深的点上,树链剖分后用线段树处理即可
    */
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N=20010;
    int top[N],nxt[N],v[N],g[N],d[N],son[N],f[N],size[N],st[N],en[N],dfn,ed;
    void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    void init(){ 
        memset(g,dfn=ed=0,sizeof(g));
        memset(v,0,sizeof(v));
        memset(nxt,0,sizeof(nxt));
        memset(son,-1,sizeof(son));
    }
    void dfs(int x){
        size[x]=1;
        for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
            f[v[i]]=x,d[v[i]]=d[x]+1;
            dfs(v[i]),size[x]+=size[v[i]];
            if(size[v[i]]>size[son[x]])son[x]=v[i];
        }
    }
    void dfs2(int x,int y){
        st[x]=++dfn;top[x]=y;
        if(son[x])dfs2(son[x],y);
        for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
        en[x]=dfn;
    }
    struct Node{int l,r;int Max;}Tree[N*3];
    void build(int x,int l,int r){
        Tree[x].l=l;Tree[x].r=r;Tree[x].Max=0;
        if(l==r)return;int mid=(l+r)>>1;
        build(x<<1,l,mid);build((x<<1)|1,mid+1,r);
    }
    void up(int x){Tree[x].Max=max(Tree[x<<1].Max,Tree[(x<<1)|1].Max);}
    void update(int x,int k,int val){
        if(Tree[x].l==k&&Tree[x].r==k){Tree[x].Max=val;return;}
        int mid=(Tree[x].l+Tree[x].r)>>1;
        if(k<=mid)update(x<<1,k,val);
        else update((x<<1)|1,k,val);
        up(x);
    }
    int query(int x,int l,int r){
        if(Tree[x].l==l&&Tree[x].r==r)return Tree[x].Max;
        int mid=(Tree[x].l+Tree[x].r)>>1;
        if(r<=mid)return query(x<<1,l,r);
        else if(l>mid)return query((x<<1)|1,l,r);
        else return max(query(x<<1,l,mid),query((x<<1)|1,mid+1,r));
    }
    int find(int x,int y){
        int tmp=0;
        for(;top[x]!=top[y];x=f[top[x]]){
            if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;}
            tmp=max(tmp,query(1,st[top[x]],st[x]));
        }if(x==y)return tmp;
        if(d[x]>d[y]){int z=x;x=y;y=z;}
        return max(tmp,query(1,st[son[x]],st[y]));
    }int e[N][3];
    int main(int n,int T){
        scanf("%d",&T);
        while(T--){
            init(); scanf("%d",&n);
            for(int i=0;i<n-1;i++){
                scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
                add(e[i][0],e[i][1]);
                add(e[i][1],e[i][0]);
            }dfs(1);dfs2(1,1);
            build(1,1,dfn);
            for(int i=0;i<n-1;i++){
                if(d[e[i][0]]>d[e[i][1]])swap(e[i][0],e[i][1]);
                update(1,st[e[i][1]],e[i][2]);
            }char op[10]; int u,w;
            while(scanf("%s",op)==1){
                if(op[0]=='D')break;
                scanf("%d%d",&u,&w);
                if(op[0]=='Q')printf("%d\n",find(u,w));
                else update(1,st[e[u-1][1]],w);
            }
        }return 0;
    }

    QTREE2

    /*
        题目大意:给出一棵边权树,要求实现树链求和以及求链上第k个元素
        题解:边权转点权后用LCT维护,注意求Qkth和sum时区别于点权树的讨论
    */
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    using namespace std;
    const int N=300010;
    namespace Link_Cut_Tree{
        vector<int> v[N],w[N];
        int f[N],son[N][2],tmp[N],size[N],val[N],sum[N]; 
        void init(){
            memset(val,0,sizeof(val));
            memset(sum,0,sizeof(sum));
            memset(f,0,sizeof(f));
            memset(son,0,sizeof(son));
            for(int i=1;i<N;i++)size[i]=1,v[i].clear(),w[i].clear();
        }
        bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
        void up(int x){ 
            sum[x]=val[x]+sum[son[x][0]]+sum[son[x][1]];
            size[x]=size[son[x][0]]+size[son[x][1]]+1;
        }
        void rotate(int x){
            int y=f[x],w=son[y][1]==x;
            son[y][w]=son[x][w^1];
            if(son[x][w^1])f[son[x][w^1]]=y;
            if(f[y]){
                int z=f[y];
                if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;
            }f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);
        }
        void splay(int x){
            int s=1,i=x,y;tmp[1]=i;
            while(!isroot(i))tmp[++s]=i=f[i];
            while(!isroot(x)){
                y=f[x]; 
                if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
                rotate(x);
            }up(x);
        }
        void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,up(x);}
        // 求边权树的链和
        int ask(int x,int y){  
            access(y),y=0;  
            int ans=0;  
            while(x){  
                splay(x);  
                if(!f[x])return sum[son[x][1]]+sum[y];  
            	son[x][1]=y; up(x);  
                x=f[y=x];  
            }  
        }  
        void dfs(int x,int fx){
            for(int i=0;i<v[x].size();i++){
                int y=v[x][i];
                if(y==fx)continue;
                f[y]=x;
                val[y]=w[x][i];
                dfs(y,x);
            }up(x);
        }
        int kth(int x,int k){
            while(size[son[x][0]]+1!=k){
                if(k<size[son[x][0]]+1)x=son[x][0];
                else{
                    k-=size[son[x][0]]+1;
                    x=son[x][1];
                }
            }return x;
        }
        // 求边权树u->v的第k个点
        int Qkth(int u,int v,int k){
            access(u),u=0;
            while(v){
                splay(v);
                if(!f[v]){  
                    if(size[son[v][1]]+1==k)return v;  
                    else if(size[son[v][1]]+1>k)return kth(son[v][1],size[son[v][1]]+1-k);  
                    else return kth(u,k-(size[son[v][1]]+1));  
                }son[v][1]=u;
                up(v); v=f[u=v]; 
            }
        }
    }
    using namespace Link_Cut_Tree;
    int T,x,y,z,k,n;
    char op[10];
    int main(){
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);  
            init();  
            for(int i=1;i<n;i++){  
                scanf("%d%d%d",&x,&y,&z);  
                  v[x].push_back(y);
                  w[x].push_back(z);
                  v[y].push_back(x);
                  w[y].push_back(z);
            }dfs(1,0);  
            while(scanf("%s",op)){  
                if(op[1]=='O')break;  
                if(op[0]=='D'){  
                    scanf("%d%d",&x,&y);  
                    printf("%d\n",ask(x,y));  
                }  
                else{    
                    scanf("%d%d%d",&x,&y,&k);  
                    printf("%d\n",Qkth(x,y,k));  
                }  
            }  
        }return 0;
    }

    QTREE3

    /*
        题目大意:给出一棵一开始都是白点的树,要求维护操作:
            1.将某个点的颜色取反(黑白互换)
            2.查询1到x的路径上第一个黑色的点
        题解:LCT维护子树中黑点的数量,对于颜色取反,则直接flap,
        对于查询操作通过access(x)将1到x这条链取出,splay上查找即可
        注意是从1到x,所以是makeroot(1),保证1节点的键值最小
    */
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N=100010;
    namespace Link_Cut_Tree{
        int f[N],son[N][2],val[N],sum[N],tmp[N];bool rev[N];
        void init(){
            memset(f,0,sizeof(f));
            memset(son,0,sizeof(son));
            memset(val,0,sizeof(val));
            memset(rev,0,sizeof(rev));
            memset(sum,0,sizeof(sum));
        } 
        bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
        void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}
        void pb(int x){if(rev[x])rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}
        void up(int x){sum[x]=sum[son[x][0]]+sum[son[x][1]]+val[x];}
        void rotate(int x){
            int y=f[x],w=son[y][1]==x;
            son[y][w]=son[x][w^1];
            if(son[x][w^1])f[son[x][w^1]]=y;
            if(f[y]){
                int z=f[y];
                if(son[z][0]==y)son[z][0]=x;else if(son[z][1]==y)son[z][1]=x;
            }f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);
        }
        void splay(int x){
            int s=1,i=x,y;tmp[1]=i;
            while(!isroot(i))tmp[++s]=i=f[i];
            while(s)pb(tmp[s--]);
            while(!isroot(x)){
                y=f[x]; 
                if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
                rotate(x);
            }up(x);
        }
        void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,up(x);}
        int root(int x){access(x);splay(x);while(son[x][0])x=son[x][0];return x;}
        void makeroot(int x){access(x);splay(x);rev1(x);}
        void link(int x,int y){makeroot(x);f[x]=y;access(x);}
        int flip(int x){makeroot(x);val[x]^=1;up(x);}
        // 查询从1->x的第一个黑点
        int ask(int x){
            makeroot(1); 
            access(x); splay(x); // splay只保证了x到根节点标记的下传
            if(!sum[x])return -1;
            while(x){
                pb(x); // 因为有makeroot操作,所以需要下传标记
                if(!sum[son[x][0]]&&val[x]==1)return x;
                else if(sum[son[x][0]])x=son[x][0];
                else x=son[x][1];
            }
        }
    }
    using namespace Link_Cut_Tree;
    int n,q,x,y;
    int main(){
        while(~scanf("%d%d",&n,&q)){
            init();
            for(int i=1;i<n;i++){
                scanf("%d%d",&x,&y);
                link(x,y);
            }
            while(q--){
                scanf("%d%d",&x,&y);
                if(x)printf("%d\n",ask(y));
                else flip(y);
            }
        }return 0;
    }

    QTREE4

    /*
        题目大意:给出一棵边权树,一开始所有点都是白点,
        要求维护两种操作:
            1.颜色取反(黑白互变)
            2.查询树上最远的两个白点之间的距离
        题解:我们维护重心树,对于每个重心维护分治层所有白点到其距离,
        将其保存在对应方向子重心的优先队列中,
        重心处另外维护一个队列保存该分治层每个子重心所产生的最大答案,即最大值加次大值,
        那么每个重心处产生的最大答案的最值就是答案,
        考虑修改问题,等价于在处理优先队列的删除问题,
        对于每个需要删除操作的优先队列,我们额外创建一个优先队列将删除元素加入其中,
        当两个队列top元素相同时同时删去即可。
    */
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int N=200010;
    const int INF=0x3f3f3f3f;
    int tot,g[N],nxt[N<<1],v[N<<1],w[N<<1];
    int TOT,G[N],NXT[N*20],V[N*20],W[N*20];
    void init(){
        memset(g,-1,sizeof(g));tot=0;
        memset(G,-1,sizeof(G));TOT=0;
    }
    void add_edge(int x,int y,int z){v[tot]=y,w[tot]=z,nxt[tot]=g[x],g[x]=tot++;}
    void ADD_EDGE(int x,int y,int z){V[TOT]=y,W[TOT]=z,NXT[TOT]=G[x],G[x]=TOT++;}
    int sum,root,size[N],dp[N],vis[N];
    void getroot(int x,int fx){
        size[x]=1; dp[x]=0;
        for(int i=g[x];~i;i=nxt[i]){
            if(!vis[v[i]]&&v[i]!=fx){
                getroot(v[i],x);
                size[x]+=size[v[i]];
                dp[x]=max(dp[x],size[v[i]]);
            }
        }dp[x]=max(dp[x],sum-size[x]);
        if(dp[x]<dp[root])root=x;
    }
    struct Que{
        priority_queue<int> Q,D;
        void clear(){
            while(!Q.empty())Q.pop();
            while(!D.empty())D.pop();
        }
        void add(int x){Q.push(x);}
        void del(int x){D.push(x);}
        int top(){
            for(;;){
                if(Q.empty())return -INF;
                else if(!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
                else return Q.top();
            }
        }
        int toptwo(){
            int x=top();
            del(x);
            int y=top();
            add(x);
            if(y==-INF)return x==-INF?x:0;
            return max(x+y,0);
        }
    }P[N],Q[N],ans;
    int dis[N],col[N];
    void getdis(int rt,int x,int fx){
        Q[rt].add(dis[x]);
        for(int i=g[x];~i;i=nxt[i]){
            if(v[i]==fx||vis[v[i]])continue;
            dis[v[i]]=dis[x]+w[i];
            getdis(rt,v[i],x);
        }
    }
    void getdeep(int rt,int x,int fx){
        ADD_EDGE(x,rt,dis[x]);
        for(int i=g[x];~i;i=nxt[i]){
            if(v[i]==fx||vis[v[i]])continue;
            dis[v[i]]=dis[x]+w[i];
            getdeep(rt,v[i],x);
        }
    }
    int belong[N];
    void build(int x,int fx,int from,int d){
        belong[x]=fx; 
        dis[x]=0; getdeep(x,x,fx); P[x].add(0);
        if(fx){
            dis[from]=d;
            getdis(x,from,fx);
            P[fx].add(Q[x].top());
        }
        vis[x]=1;
        for(int i=g[x];~i;i=nxt[i])if(!vis[v[i]]){
            root=0; sum=size[v[i]];
            getroot(v[i],x);
            build(root,x,v[i],w[i]);
        }
        ans.add(P[x].toptwo());
    }
    void change(int rt){
        int a=P[rt].toptwo();
        if(col[rt])P[rt].add(0);
        else P[rt].del(0);
        int b=P[rt].toptwo();
        if(a!=b)ans.del(a),ans.add(b);
        int x=rt;
        for(int i=G[rt];~NXT[i];i=NXT[i]){
            int y=V[NXT[i]],len=W[NXT[i]];
            x=V[i];
            a=Q[x].top();
            if(col[rt])Q[x].add(len);
            else Q[x].del(len);
            b=Q[x].top();
            if(a!=b){
                int c=P[y].toptwo();
                P[y].del(a),P[y].add(b);
                int d=P[y].toptwo();
                if(c!=d)ans.del(c),ans.add(d);
            }
        }
    }
    int n,m,a,b,c,x;
    char op[10];
    int main(){
        scanf("%d",&n); init();
        for(int i=1;i<=n;i++)col[i]=1;
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&a,&b,&c);
            add_edge(a,b,c);
            add_edge(b,a,c);
        }
        memset(vis,0,sizeof(vis));
        dp[root=0]=sum=n;
        getroot(1,0);
        build(root,0,0,0);
        scanf("%d",&m);
        int cnt=n;
        while(m--){
            scanf("%s",op);
            if(op[0]=='A'){
                if(cnt)printf("%d\n",ans.top());
                else puts("They have disappeared.");
            }else{
                scanf("%d",&x);
                col[x]^=1;
                if(col[x])cnt++;
                else cnt--;
                change(x);
            }
        }return 0;
    }

    QTREE5

    /*
        题目大意:给出一棵树,边权均为1,一开始所有点都是白点,
        要求维护两种操作:
            1.颜色取反(黑白互变)
            2.查询树上某点距离最近的白点与其距离
        题解:我们维护重心树,对于每个重心维护分治层所有白点到其距离,
        将其保存在对应方向子重心的优先队列中,
        重心处另外维护一个队列表示每个子重心的最小答案,
        考虑修改问题,等价于在处理优先队列的删除问题,
        对于每个需要删除操作的优先队列,我们额外创建一个优先队列将删除元素加入其中,
        当两个队列top元素相同时同时删去即可。
        对于查询操作,我们沿着重心链用经过每个重心的最优值更新答案
    */
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int N=200010;
    const int INF=0x3f3f3f3f;
    int tot,g[N],nxt[N<<1],v[N<<1],w[N<<1];
    int TOT,G[N],NXT[N*20],V[N*20],W[N*20];
    void init(){
        memset(g,-1,sizeof(g));tot=0;
        memset(G,-1,sizeof(G));TOT=0;
    }
    void add_edge(int x,int y,int z){v[tot]=y,w[tot]=z,nxt[tot]=g[x],g[x]=tot++;}
    void ADD_EDGE(int x,int y,int z){V[TOT]=y,W[TOT]=z,NXT[TOT]=G[x],G[x]=TOT++;}
    int sum,root,size[N],dp[N],vis[N];
    void getroot(int x,int fx){
        size[x]=1; dp[x]=0;
        for(int i=g[x];~i;i=nxt[i]){
            if(!vis[v[i]]&&v[i]!=fx){
                getroot(v[i],x);
                size[x]+=size[v[i]];
                dp[x]=max(dp[x],size[v[i]]);
            }
        }dp[x]=max(dp[x],sum-size[x]);
        if(dp[x]<dp[root])root=x;
    }
    struct Que{
        priority_queue<int,vector<int>,greater<int> > Q,D;
        void clear(){
            while(!Q.empty())Q.pop();
            while(!D.empty())D.pop();
        }
        void add(int x){Q.push(x);}
        void del(int x){D.push(x);}
        int top(){
            for(;;){
                if(Q.empty())return INF;
                else if(!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
                else return Q.top();
            }
        }
    }P[N],Q[N];
    int dis[N],col[N];
    void getdis(int rt,int x,int fx){
        for(int i=g[x];~i;i=nxt[i]){
            if(v[i]==fx||vis[v[i]])continue;
            dis[v[i]]=dis[x]+w[i];
            getdis(rt,v[i],x);
        }
    }
    void getdeep(int rt,int x,int fx){
        ADD_EDGE(x,rt,dis[x]);
        for(int i=g[x];~i;i=nxt[i]){
            if(v[i]==fx||vis[v[i]])continue;
            dis[v[i]]=dis[x]+w[i];
            getdeep(rt,v[i],x);
        }
    }
    int belong[N];
    void build(int x,int fx,int from,int d){
        belong[x]=fx; 
        dis[x]=0; getdeep(x,x,fx); 
        if(fx){
            dis[from]=d;
            getdis(x,from,fx);
        }
        vis[x]=1;
        for(int i=g[x];~i;i=nxt[i])if(!vis[v[i]]){
            root=0; sum=size[v[i]];
            getroot(v[i],x);
            build(root,x,v[i],w[i]);
        }
    }
    void change(int rt){
        if(col[rt])P[rt].add(0);
        else P[rt].del(0);
        int x=rt;
        for(int i=G[rt];~NXT[i];i=NXT[i]){
            int y=V[NXT[i]],len=W[NXT[i]];
            x=V[i];
            int a=Q[x].top();
            if(col[rt])Q[x].add(len);
            else Q[x].del(len);
            int b=Q[x].top();
            if(a!=b)P[y].del(a),P[y].add(b);
        }
    }
    int ask(int rt){
        int ans=INF;
        for(int i=G[rt];~i;i=NXT[i]){
            int x=V[i],len=W[i];
            int a=P[x].top();
            if(a+len<ans)ans=a+len;
        }
        return ans;
    }
    int n,m,a,b,c,x,op;
    int main(){
        scanf("%d",&n); init();
        for(int i=1;i<=n;i++)col[i]=0;
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            add_edge(a,b,1);
            add_edge(b,a,1);
        }
        memset(vis,0,sizeof(vis));
        dp[root=0]=sum=n;
        getroot(1,0);
        build(root,0,0,0);
        scanf("%d",&m);
        int cnt=0;
        while(m--){
            scanf("%d%d",&op,&x);
            if(op==1){
                if(cnt)printf("%d\n",ask(x));
                else puts("-1");
            }else{
                col[x]^=1;
                if(col[x])cnt++;
                else cnt--;
                change(x);
            }
        }return 0;
    }

    QTREE6

    /*
        题目大意:给出一棵树,一开始树上点均为黑色,要求维护操作
            1.翻转某点的颜色(黑白互换),
            2.查询某个点所在连通块(颜色相同则连通)大小
        题解:我们分别维护黑点LCT和白点LCT,当一个点从黑变白时,
        将其从黑点LCT中与父节点断开,然后在白点LCT中与父节点相连,
        这样我们就保证了每个连通块在LCT中只有父节点是不同色的而其余一定是连通的。
        考虑用LCT维护子树信息,根据在LCT上的连接情况,我们将点的儿子分为实儿子和虚儿子
        实儿子是原本树结构上相连的点,实儿子的子树为实子树,虚儿子的子树为虚子树
        x的LCT子树的信息和等于x的实儿子的LCT子树信息和加上x的虚子树的信息和加上x自己
        在进行access操作时,我们会有更换一个点的x右儿子的操作,
        这时我们要把x原来的右儿子的LCT子树信息加入x的虚子树信息,
        把x的新的右儿子的LCT子树信息从x的虚子树信息中减去
        同时在link x到y的时候,我们需要对y进行access再splay
        这样就只会对y的虚子树信息和LCT子树信息产生影响,而不会影响到y的祖先节点
    */
    #include <cstdio>
    #include <algorithm>
    #include <set>
    const int N=100010; 
    using namespace std;
    int n,m,i,k,x,y,c[N],fa[N],g[N],v[N<<1],nxt[N<<1],ed;
    struct LCT{
        int son[N][2],f[N],sum[N],s[N];
        bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
        void up(int x){sum[x]=1+sum[son[x][0]]+sum[son[x][1]]+s[x];}
        void rotate(int x){
            int y=f[x],w=son[y][1]==x;
            son[y][w]=son[x][w^1];
            if(son[x][w^1])f[son[x][w^1]]=y;
            if(f[y]){
                int z=f[y];
                if(son[z][0]==y)son[z][0]=x;
                if(son[z][1]==y)son[z][1]=x;
            }f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);
        }
        void splay(int x){
            while(!isroot(x)){
                int y=f[x];
                if(!isroot(y)){
                    if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);
                    else rotate(y);
                }rotate(x);
            }up(x);
        }
        void access(int x){
            for(int y=0;x;y=x,x=f[x]){
                splay(x);
                if(son[x][1])s[x]+=sum[son[x][1]];
                if(son[x][1]=y)s[x]-=sum[y];
                up(x);
            }
        }
        int root(int x){access(x);splay(x);while(son[x][0])x=son[x][0];return x;}
        void link(int x){access(fa[x]);splay(fa[x]);splay(x);son[fa[x]][1]=x;up(f[x]=fa[x]);}
        void cut(int x){access(x);splay(x);f[son[x][0]]=0;son[x][0]=0;up(x);}
        int ask(int x){splay(x=root(x));return sum[son[x][1]];}
    }T[2];
    void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    void dfs(int x){
        for(int i=g[x];i;i=nxt[i])if(v[i]!=fa[x]){
            fa[v[i]]=T[c[v[i]]].f[v[i]]=x;
            dfs(v[i]);
            T[c[v[i]]].s[x]+=T[c[v[i]]].sum[v[i]];
        }T[0].up(x),T[1].up(x);
    }
    void read(int&a){
        char c;
        while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';
        while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
    }
    int main(){
         read(n);
         for(i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);
         for(i=1;i<=n;i++)c[i]=0;
         fa[1]=T[c[1]].f[1]=n+1;dfs(1);
         T[c[1]].s[n+1]+=T[c[1]].sum[1];read(m);
         while(m--){
             read(k);read(x);
             if(!k)printf("%d\n",T[c[x]].ask(x));
             else T[c[x]].cut(x),T[c[x]^=1].link(x);
         }return 0;
    }

    QTREE7

    /*
        题目大意:给出一棵树,树上每个点为黑色或者白色,每个点有个点权,
        我们认为树上颜色相同并通过边连接的块为连通块
        要求维护操作:
            0.查询x所在连通块中权值最大的点
            1.翻转某点的颜色(黑白互换)
            2.改变某点的权值
        题解:我们分别维护黑点LCT和白点LCT,当一个点从黑变白时,
        将其从黑点LCT中与父节点断开,然后在白点LCT中与父节点相连,
        这样我们就保证了每个连通块在LCT中只有父节点是不同色的而其余一定是连通的。
        考虑用LCT维护子树信息,根据在LCT上的连接情况,我们将点的儿子分为实儿子和虚儿子
        实儿子是原本树结构上相连的点,实儿子的子树为实子树,虚儿子的子树为虚子树
        x的LCT子树的信息和等于x的实儿子的LCT子树信息和加上x的虚子树的信息和加上x自己
        在进行access操作时,我们会有更换一个点的x右儿子的操作,
        这时我们要把x原来的右儿子的LCT子树信息加入x的虚子树信息,
        把x的新的右儿子的LCT子树信息从x的虚子树信息中减去
        同时在link x到y的时候,我们需要对y进行access再splay
        这样就只会对y的虚子树信息和LCT子树信息产生影响,而不会影响到y的祖先节点
        因为要维护的信息是极值,因此我们要用multiset来维护虚子树信息
    */
    #include <cstdio>
    #include <algorithm>
    #include <ctype.h>
    #include <set>
    const int N=100010; 
    using namespace std;
    int n,m,k,x,y,c[N],fa[N],g[N],v[N<<1],nxt[N<<1],ed;
    struct LCT{
        int son[N][2],f[N],val[N],mx[N];
        multiset<int> s[N];
        bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}
        void up(int x){
            mx[x]=val[x];
            if(s[x].size())mx[x]=max(mx[x],*s[x].rbegin());
            if(son[x][0])mx[x]=max(mx[x],mx[son[x][0]]);
            if(son[x][1])mx[x]=max(mx[x],mx[son[x][1]]);
        }
        void rotate(int x){
            int y=f[x],w=son[y][1]==x;
            son[y][w]=son[x][w^1];
            if(son[x][w^1])f[son[x][w^1]]=y;
            if(f[y]){
                int z=f[y];
                if(son[z][0]==y)son[z][0]=x;
                if(son[z][1]==y)son[z][1]=x;
            }f[x]=f[y];f[y]=x;son[x][w^1]=y;up(y);
        }
        void splay(int x){
            while(!isroot(x)){
                int y=f[x];
                if(!isroot(y)){
                    if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);
                    else rotate(y);
                }rotate(x);
            }up(x);
        }
        void access(int x){
            for(int y=0;x;y=x,x=f[x]){
                splay(x);
                if(son[x][1])s[x].insert(mx[son[x][1]]);
                if(son[x][1]=y)s[x].erase(s[x].find(mx[y]));
                up(x);
            }
        }
        int root(int x){access(x);splay(x);while(son[x][0])x=son[x][0];return x;}
        void link(int x){access(fa[x]);splay(fa[x]);splay(x);son[fa[x]][1]=x;up(f[x]=fa[x]);}
        void cut(int x){access(x);splay(x);f[son[x][0]]=0;son[x][0]=0;up(x);}
        int ask(int x){
    		int t=c[x]; splay(x=root(x));
    		return t==c[x]?mx[x]:mx[son[x][1]];
    	}
        void modify(int x,int v){access(x),splay(x),val[x]=v,up(x);}  
    }T[2];
    void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    void dfs(int x){
        for(int i=g[x];i;i=nxt[i])if(v[i]!=fa[x]){
            fa[v[i]]=T[c[v[i]]].f[v[i]]=x;
            dfs(v[i]);
            T[c[v[i]]].s[x].insert(T[c[v[i]]].mx[v[i]]);
        }T[0].up(x),T[1].up(x);
    }
    void read(int &x){  
        char ch;
        for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());  
        int t;if(ch=='-')t=-1,ch=getchar();else t=1;  
        for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';  
        x=x*t;  
    }  
    int main(){
         read(n);
         for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);
         for(int i=1;i<=n;i++)read(c[i]);  
         for(int i=1;i<=n;i++)read(T[0].val[i]),T[1].val[i]=T[0].val[i];  
         dfs(1); read(m);
         while(m--){
             read(k);read(x);
             if(k==0)printf("%d\n",T[c[x]].ask(x));
             else if(k==1)T[c[x]].cut(x),T[c[x]^=1].link(x);
             else if(k==2)read(y),T[0].modify(x,y),T[1].modify(x,y);
         }return 0;
    }

    转载于:https://www.cnblogs.com/forever97/p/QTREE.html

    展开全文
  • QTREE系列题解

    2019-10-02 07:05:03
    打了快一星期的qtree终于打完了- - (其实还有两题改不出来弃疗了QAQ) orz神AK一星期前就虐完QTREE 避免忘记还是简单写下题解吧0 0 QTREE1 题意: 给出一颗带边权树 一个操作:修改边权 还有一个询问:求x...
  • Qtree LCT系列

    2019-07-19 21:19:55
    Qtree1,2,3暂缺 Qtree4思路 总是有机房大佬问我怎么做(抄题解不就好了吗?),那我就讲一讲我紊乱的思路吧。 应该不难想到边权下放到子节点,有了这个基础,我们对细节的处理就不用那么模糊了。 先上定义: ...
  • SPOJ QTREE 系列

    千次阅读 2015-08-04 00:14:26
    QTREE Query on a tree 树链剖分:QTREE LCT:QTREE QTREE2 Query on a tree II 倍增LCA:QTREE2 PTO7J Query on a tree III dfs序+主席树:QTREE3 QTREE4 Query on a tree IV 边分治+堆:QTREE4
  • QTREE
  • SPOJ Qtree系列

    2019-10-07 07:53:37
    Qtree1 将边权变为这条边连接的两个点中深度更深的点的点权,这样就可以变为带修改链上最大点权。直接树链剖分即可。 下面是一份C语言代码 #include<stdio.h> #include<string.h> #define MAXN 10001 ...
  • qtree源代码及示例

    2012-12-11 17:49:58
    qtree组件源代码、api文档以及示例
  • QTREE
  • SPOJ QTREE4 Query on a tree IV(边分治)

    千次阅读 2016-03-31 23:29:57
    qtree
  • QTREE
  • QTREE系列题目总结

    2019-01-03 17:24:00
    $QTREE$ 就是一套树上数据结构练习题。 这套题貌似来源于 $SPOJ$,我是在 $luogu$ 看到的。 $QTREE1$ 题意 一棵 $n$ 个点的带边权树,要求支持 单边改权值 和 询问路径边权和。 题解 树链剖分裸题。 $...
  • SPOJ QTREE7

    2018-03-26 19:32:00
    题意 一棵树,每个点初始有个点权和颜色 \(0 \ u\) :询问所有\(u,v\) 路径上的最大点权,要满足\(u,v\) 路径上所有点的颜色都相同 $1 u \(:反转\)u$ 的颜色 \(2 \ u \ w\) :把\(u\) 的点权改成...和\(QTREE6\)一样,黑...
  • 关于SPOJ 中的qtree问题的一类解法和深入思考
  • Qtree4题意:维护一颗树,每个点有颜色(黑/白),最开始均为黑色。满足两种操作: 1,翻转某个点的颜色。 2,询问整棵树上距离最远的两个白色点的距离(带权边)分析线段树存储3个信息: 1,子树内到达左端点的...
  • QTREE 解法的一些研究 信息学 QTREE 解法的一些研究 信息学 QTREE 解法的一些研究 信息学 QTREE 解法的一些研究 信息学
  • P4114 Qtree1

    2019-09-21 04:59:49
    P4114 Qtree1 题解 树链剖分的恶心题目 1.读入边,连边存边 2.两遍DFS 第一遍找出每个点的重儿子 son fa size 第二遍更新 dfn dep top 3.把边权放到深度较大的结点上 4.线段树建树存边 5.线段树单点修改...
  • SPOJ QTree1树链剖分版LCT版SPOJ QTree2树链剖分版LCT版...树链剖分版LCT版SPOJ QTree3主席树版本SPOJ QTree4树链剖分版LCT版SPOJ QTree5树链剖分版点分治版LCT版SPOJ QTree6树链剖分版LCT版SPOJ QTree7树链剖分版LCT版
  • SPOJ2666 QTREE4

    2019-10-02 13:23:40
    我是萌萌的传送门 我是另一个萌萌的传送...昨天听ztc讲了讲树分治,下午心血来潮想写QTREE4……写的是边分治,然后调了一晚上没调出来,后来发现换一个点作根建树就A了(COGS数据弱……)……然而交到vjudge上还是WA...
  • [Spoj16580]Qtree7

    2018-03-10 23:11:30
    这题是Qtree6Qtree6Qtree6稍微加强了一下,思想和Qtree6Qtree6Qtree6一样,就是维护的信息不同 其实维护颜色相同的联通块基本上是这个套路稳了 这道题维护子树信息的话要开一个setsetset维护虚儿子的最大值 推荐先...
  • spoj qtree IV

    2015-01-06 22:53:00
    2666. Query on a tree IV...Problem code: QTREE4 You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to ...
  • Luogu4114 Qtree1

    2018-04-28 18:26:27
    Qtree1 题目背景 数据规模和spoj上有所不同 题目描述 给定一棵n个节点的树,有两个操作: CHANGE i ti 把第i条边的边权变成ti QUERY a b 输出从a到b的路径中最大的边权,当a=b的时候,输出0 输入输出...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,650
精华内容 660
关键字:

Qtree