QTREE系列题解

打了快一星期的qtree终于打完了- - （其实还有两题改不出来弃疗了QAQ）

orz神AK一星期前就虐完QTREE

避免忘记还是简单写下题解吧0 0

QTREE1

题意：

给出一颗带边权树

一个操作：修改边权

还有一个询问：求x到y路径上边权最大值

树链剖分模版题- -blabla

代码：

 #include <cstdio>

 #include <cstring>

 const int N=;

 struct inli{

     int next,data,lon;

     inli(const int a=,const int b=,const int c=):

         next(a),data(b),lon(c){}

 }line[N*];

 struct info{

     int x,y;

     info(const int a=,const int b=):

         x(a),y(b){}

 }sline[N];

 int n,t,nl,dfss,back[N],tree[N*],deep[N],num[N],hard[N],dfn[N],fl[N],fat[N],gr[N],son[N];

 int st,si;

 char s[];

 int max(int x,int y){ return x>y ? x : y; }

 void swap(int &x,int &y){ int t=x; x=y,y=t; }

 void clean(){

     nl=dfss=;

     memset(son,,sizeof(son));

     memset(hard,,sizeof(hard));

     memset(tree,,sizeof(tree));

 }

 void makehard(int t){

     num[t]=;

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t]){

         int ne=line[i].data;

         fat[ne]=t;

         deep[ne]=deep[t]+;

         fl[ne]=line[i].lon;

         makehard(ne);

         num[t]+=num[ne];

         if (num[hard[t]]<num[ne]) hard[t]=ne;

     }

 }

 void dfs(int t,int gra){

     dfn[t]=++dfss;

     back[dfss]=t;

     gr[t]=gra;

     if (hard[t]) dfs(hard[t],gra);

     for (int i=son[t];i;i=line[i].next){

         int ne=line[i].data;

         if (ne!=fat[t] && ne!=hard[t]) dfs(ne,ne);

     }

 }

 void build(int l,int r,int rt){

     if (l==r-){

         tree[rt]=fl[back[r]];

         return;

     }

     int mid=(l+r)/;

     build(l,mid,rt*);

     build(mid,r,rt*+);

     tree[rt]=max(tree[rt*],tree[rt*+]);

 }

 int getmax(int l,int r,int rt,int x,int y){

     if (x==y) return ;

     if (x<=l && r<=y) return tree[rt];

     int mid=(l+r)/,res=;

     if (x<mid) res=max(res,getmax(l,mid,rt*,x,y));

     if (mid<y) res=max(res,getmax(mid,r,rt*+,x,y));

     return res;

 }

 int getans(int x,int y){

     if (x==y) return ;

     if (gr[x]==gr[y]){

         if (deep[x]>deep[y]) swap(x,y);

         return getmax(,n,,dfn[x],dfn[y]);

     }

     if (deep[gr[x]]<deep[gr[y]]) swap(x,y);

     return max(getans(fat[gr[x]],y),max(getmax(,n,,dfn[gr[x]],dfn[x]),fl[gr[x]]));

 }

 void change2(int l,int r,int rt,int x,int y){

     if (l+==r) return (void)(tree[rt]=y);

     int mid=(l+r)/;

     if (x<mid) change2(l,mid,rt*,x,y);

     else change2(mid,r,rt*+,x,y);

     tree[rt]=max(tree[rt*],tree[rt*+]);

 }

 void change(int t,int s){

     int x=sline[t].x,y=sline[t].y;

     if (deep[x]>deep[y]) swap(x,y);

     if (gr[x]==gr[y]) change2(,n,,dfn[x],s);

     else fl[y]=s;

 }

 int main(){

     freopen("spoj375.in","r",stdin);

     freopen("spoj375.out","w",stdout);

     for (scanf("%d",&t);t;t--){

         clean();

         scanf("%d\n",&n);

         int x,y,z;

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

             scanf("%d%d%d\n",&x,&y,&z);

             line[++nl]=inli(son[x],y,z),son[x]=nl;

             line[++nl]=inli(son[y],x,z),son[y]=nl;

             sline[i]=info(x,y);

         }

         makehard();

         dfs(,);

         build(,n,);

         int i=;

         while (){

             si=++i;

             st=t;

             if (i==)

             i=;

             if (t==)

             t=;

             if (t== && i==)

             t=;

             scanf("%s",s);

             if (s[]=='Q'){

                 scanf("%d%d\n",&x,&y);

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

             }

             if (s[]=='C'){

                 scanf("%d%d\n",&x,&y);

                 change(x,y);

             }

             if (s[]=='D') break;

             if (n==)

             n=;

         }

     }

     fclose(stdin);

     fclose(stdout);

 }

QTREE2

题意：

给出一颗带边权树两个询问

1.求x到y路径上边权和

2.求x到y路径上的第k条边的边权

边权和还是树链剖分模版- -

求第k条边刚想了一下貌似树剖也能做但是我是用倍增的

代码：

 #include <cstdio>

 #include <cstring>

 const int N=;

 struct inli{

     int next,data,lon;

     inli(const int a=,const int b=,const int c=):

         next(a),data(b),lon(c){}

 }line[N*];

 int t,n,nl,deep[N],son[N],fat[N][],dis[N][];

 char s[];

 void swap(int &x,int &y){ int t=x; x=y,y=t; }

 void clean(){

     nl=;

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

         son[i]=;

         memset(fat[i],,sizeof(fat[i]));

     }

 }

 void makefat(int t){

     for (int i=;fat[fat[t][i-]][i-];++i){

         fat[t][i]=fat[fat[t][i-]][i-];

         dis[t][i]=dis[t][i-]+dis[fat[t][i-]][i-];

     }

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t][]){

         int ne=line[i].data;

         deep[ne]=deep[t]+;

         fat[ne][]=t;

         dis[ne][]=line[i].lon;

         makefat(ne);

     }

 }

 int getdis(int x,int y){

     if (x==y) return ;

     if (deep[x]!=deep[y]){

         if (deep[x]<deep[y]) swap(x,y);

         int i=;

         for (;deep[fat[x][i]]>=deep[y] && fat[x][i];++i);

         --i;

         return dis[x][i]+getdis(fat[x][i],y);

     }

     if (fat[x][]==fat[y][]) return dis[x][]+dis[y][];

     int i=;

     for (;fat[x][i]!=fat[y][i] && fat[x][i];++i);

     --i;

     return dis[x][i]+dis[y][i]+getdis(fat[x][i],fat[y][i]);

 }

 int getgr(int x,int y){

     if (x==y) return x;

     if (deep[x]!=deep[y]){

         if (deep[x]<deep[y]) swap(x,y);

         int i=;

         for (;deep[fat[x][i]]>=deep[y] && fat[x][i];++i);

         --i;

         return getgr(fat[x][i],y);

     }

     if (fat[x][]==fat[y][]) return fat[x][];

     int i=;

     for (;fat[x][i]!=fat[y][i] && fat[x][i];++i);

     --i;

     return getgr(fat[x][i],fat[y][i]);

 }

 int getans(int t,int s){

     if (s==) return t;

     int i=;

     for (;deep[t]-deep[fat[t][i]]+<=s && fat[t][i];++i);

     --i;

     return getans(fat[t][i],s-(deep[t]-deep[fat[t][i]]));

 }

 int main(){

     freopen("spoj913.in","r",stdin);

     freopen("spoj913.out","w",stdout);

     for (scanf("%d",&t);t;t--){

         scanf("%d\n",&n);

         clean();

         int x,y,z;

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

             scanf("%d%d%d\n",&x,&y,&z);

             line[++nl]=inli(son[x],y,z),son[x]=nl;

             line[++nl]=inli(son[y],x,z),son[y]=nl;

         }

         makefat();

         while (){

             scanf("%s",s);

             if (s[]=='I'){

                 scanf("%d%d\n",&x,&y);

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

             }

             if (s[]=='K'){

                 scanf("%d%d%d\n",&x,&y,&z);

                 int gr=getgr(x,y);

                 if (deep[x]-deep[gr]+<z){

                     swap(x,y);

                     z=deep[x]+deep[y]-deep[gr]*+-z;

                 }

                 printf("%d\n",getans(x,z));

             }

             if (s[]=='O') break;

         }

         puts("");

     }

     fclose(stdin);

     fclose(stdout);

 }

QTREE3

题意：

给出一颗点初始全白的树

一个操作：修改点的颜色

一个询问：求1到点x的最近黑点没有则输出-1

这题我觉得能用动态树做

询问的时候把x access到根 splay上维护深度最小的黑点

树链剖分也可以做线段树维护最前面的黑点即可（貌似比较简单- -）

这题我貌似就yy了一下没打- -

QTREE4

题意：

给出一颗点初始全白的带边权树

一个操作：修改点的颜色

一个询问：求最远的两个白色点的距离

QAQ这题被spoj卡时了啊根本调不出来- -

其实这题好像是去湖南培训的一道题的弱化版- - 我竟然没想出来orz

我的做法是点分治+3*堆

我们定义某重心的子树的重心是该重心的重儿子反之重父亲

维护第一个堆que1维护该点管辖范围内的点到该点重父亲的距离最大值

第二个堆que2维护该点的每个重儿子的que1的堆顶的最大值（如果该点为白点要插入一个dis为0的值）

每个que2的前2大的距离和即为两白点经过该点答案

第三个堆ans3就维护所有的que2的前2大的距离和的最大值

因为我用的是priority_queue 所以不支持删除- - 于是我就每个对打了一个时间戳

一修改3个堆一个套一个全部要改整个世界格局混乱orz 思路不清晰就很容易晕

这题我打了3天啊QAQ（最后还没调出来←_←）

这题没A就不贴代码了- -

QTREE5

题意：

给出一颗点初始全白的带边权树

一个操作：修改点的颜色

一个询问：求离点x最远的白点的距离

这题和上题做法差不多枚举管辖范围包括x的重心即可

因为上一题被卡时了 - - 这题也不敢打orz

QTREE6

题意：

给出一颗点初始全白的树

一个操作：修改点的颜色

一个询问：求点x与多少点相连两点相连条是这两点的路径上的点都与点x的颜色相同

这题我是用树链剖分做的

维护f[2][i]表示i点为黑色或白色时 i的子树中与i相连的点的个数

那么x点的答案就是x点的最浅相连祖先的f[col[x]]值

当修改某点的颜色时就修改该点到最浅相连祖先的父亲的f值即可

这题也可以用动态树做

详见QTREE7- - 233为什么和神ak写的一样

代码：

 #include <cstdio>

 const int N=;

 struct inli{

     int next,data;

     inli(const int a=,const int b=):

         next(a),data(b){}

 }line[N*];

 int n,m,nl,dfss,deep[N],gr[N],hard[N],num[N],back[N],dfn[N],son[N],tree[][N*],fat[N][],coltree[N*],col[N];

 void makehard(int t){

     for (int i=;fat[fat[t][i-]][i-];++i) fat[t][i]=fat[fat[t][i-]][i-];

     num[t]=;

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t][]){

         int ne=line[i].data;

         fat[ne][]=t;

         deep[ne]=deep[t]+;

         makehard(ne);

         num[t]+=num[ne];

         if (num[ne]>num[hard[t]]) hard[t]=ne;

     }

 }

 void dfs(int t,int gra){

     gr[t]=gra;

     dfn[t]=++dfss;

     back[dfss]=t;

     if (hard[t]) dfs(hard[t],gra);

     for (int i=son[t];i;i=line[i].next){

         int ne=line[i].data;

         if (ne!=fat[t][] && ne!=hard[t]) dfs(ne,ne);

     }

 }

 void pushdown(int t){

     tree[][t*]+=tree[][t];

     tree[][t*+]+=tree[][t];

     tree[][t]=;

     tree[][t*]+=tree[][t];

     tree[][t*+]+=tree[][t];

     tree[][t]=;

 }

 void build(int l,int r,int rt){

     if (l==r){

         tree[][rt]=num[back[l]];

         tree[][rt]=;

         return;

     }

     int mid=(l+r)/;

     build(l,mid,rt*);

     build(mid+,r,rt*+);

 }

 int getgr(int l,int r,int rt,int x,int y,int z){

     int mid=(l+r)/,res;

     if (x<=l && r<=y){

         if (coltree[rt]==z) return l;

         if (l==r) return -;

         if (coltree[rt*+]!=z) return getgr(mid+,r,rt*+,x,y,z);

         res=getgr(l,mid,rt*,x,y,z);

         return res==- ? mid+ : res;

     }

     if (y<=mid) return getgr(l,mid,rt*,x,y,z);

     if (x>mid) return getgr(mid+,r,rt*+,x,y,z);

     res=getgr(mid+,r,rt*+,x,y,z);

     if (res==-) return -;

     if (res>mid+) return res;

     res=getgr(l,mid,rt*,x,y,z);

     return res==- ? mid+ : res;

 }

 int getans(int l,int r,int rt,int x,int y){

     if (l==r) return tree[y][rt];

     int mid=(l+r)/;

     pushdown(rt);

     if (x<=mid) return getans(l,mid,rt*,x,y);

     else return getans(mid+,r,rt*+,x,y);

 }

 void addtree(int l,int r,int rt,int x,int y,int z,int co){

     if (x<=l && r<=y) return (void)(tree[co][rt]+=z);

     int mid=(l+r)/;

     pushdown(rt);

     if (x<=mid) addtree(l,mid,rt*,x,y,z,co);

     if (mid<y) addtree(mid+,r,rt*+,x,y,z,co);

 }

 void changecol(int l,int r,int rt,int x){

     if (l==r) return (void)(coltree[rt]^=);

     int mid=(l+r)/;

     if (x<=mid) changecol(l,mid,rt*,x);

     else changecol(mid+,r,rt*+,x);

     coltree[rt]=coltree[rt*]==coltree[rt*+] ? coltree[rt*] : -;

 }

 int getfat(int t,int co){

     if (!fat[t][] || col[fat[t][]]!=co)  return t;

     int save=back[getgr(,n,,dfn[gr[t]],dfn[t],co)];

     if (save!=gr[t] || !fat[gr[t]][] || col[fat[gr[t]][]]!=co) return save;

     else return getfat(fat[gr[t]][],co);

 }

 void add(int co,int x,int y,int s){

     if (deep[x]>deep[y]) return;

     if (gr[x]==gr[y]){

         addtree(,n,,dfn[x],dfn[y],s,co);

         return;

     }

     addtree(,n,,dfn[gr[y]],dfn[y],s,co);

     add(co,x,fat[gr[y]][],s);

 }

 void change(int t){

     int p1=getans(,n,,dfn[t],col[t]),p2=getans(,n,,dfn[t],col[t]^);

     /*if (fat[t][0]){

         if (col[fat[t][0]]==col[t]) add(col[t]^1,fat[t][0],fat[t][0],p2);

         else add(col[t],fat[t][0],fat[t][0],-p1);

     }*/

     int fa=getfat(t,col[t]);

     if (fat[fa][]) fa=fat[fa][];

     add(col[t],fa,fat[t][],-p1);

     col[t]^=;

     changecol(,n,,dfn[t]);

     fa=getfat(t,col[t]);

     if (fat[fa][]) fa=fat[fa][];

     add(col[t],fa,fat[t][],p2);

 }

 int main(){

     freopen("spoj16549.in","r",stdin);

     freopen("spoj16549.out","w",stdout);

     scanf("%d",&n);

     for (int x,y,i=;i<n;i++){

         scanf("%d%d",&x,&y);

         line[++nl]=inli(son[x],y),son[x]=nl;

         line[++nl]=inli(son[y],x),son[y]=nl;

     }

     deep[]=;

     makehard();

     dfs(,);

     build(,n,);

     scanf("%d",&m);

     for (int x,y,i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         if (i==)

         i=;

         if (x) change(y);

         else printf("%d\n",getans(,n,,dfn[getfat(y,col[y])],col[y]));

     }

     fclose(stdin);

     fclose(stdout);

 }

QTREE7

题意：

给出一颗点为黑色或白色的带点权的树

两个操作：

1.修改点的颜色

2.修改点权

一个询问：

求点与x相连的点的最大点权两点相连条是这两点的路径上的点都与点x的颜色相同

把黑点和白点建成两颗树同色的相连点就在同一颗树上

用set维护某点的轻边子树的最大值（取每个轻边子树的最大点权存进set）

再用动态树splay维护重边上的点最大值

询问时把该点access到根再splay求出答案即可

access的时候要注意当修改重边时 set要删除原轻边的最大值加上原重边的最大值

修改点权也很好处理 - -稍微想想就知道了

修改颜色则需要从某颜色的树上cut下一个点再在另外颜色的树上link上一个点

但是当图为菊花图时link上的点的轻边个数可能有O(n)个在set上一个个插入一次操作就需要O(nlogn) 显然tle

orz神ak想到一种特别好的方法

在黑数上如果某点有个儿子的颜色为黑色就保留该点白树同理这样每次修改在set上就只会插入或删除一个点就能过了

代码：

 #include <cstdio>

 #include <set>

 using namespace std;

 const int N=;

 struct intr{

     int fat,lc,rc,t,max,root;

     intr(const int a=,const int b=,const int c=,const int d=,const int e=,const int f=):

         fat(a),lc(b),rc(c),t(d),max(e),root(f){}

 };

 struct inli{

     int next,data;

     inli(const int a=,const int b=):

         next(a),data(b){}

 }line[N*];

 int n,m,nl,son[N],col[N],fat[N];

 int max(int x,int y){ return x>y ? x : y; }

 struct LCT{

     intr tree[N];

     int xx;

     multiset <int> se[N];

     void clean(){ tree[]=intr(); }

     void maintain(int t){

         tree[t].max=tree[t].t;

         if (se[t].size()) tree[t].max=max(tree[t].max,*se[t].rbegin());

         if (tree[t].lc) tree[t].max=max(tree[t].max,tree[tree[t].lc].max);

         if (tree[t].rc) tree[t].max=max(tree[t].max,tree[tree[t].rc].max);

     }

     void left(int t){

         int fa=tree[t].fat,r=tree[t].rc;

         tree[t].rc=tree[r].lc,tree[tree[r].lc].fat=t;

         tree[r].lc=t,tree[t].fat=r;

         if (tree[t].root) tree[t].root=,tree[r].root=;

         else if (tree[fa].lc==t) tree[fa].lc=r;

         else tree[fa].rc=r;

         tree[r].fat=fa;

         clean();

         maintain(t);

         maintain(r);

     }

     void right(int t){

         int fa=tree[t].fat,l=tree[t].lc;

         tree[t].lc=tree[l].rc,tree[tree[l].rc].fat=t;

         tree[l].rc=t,tree[t].fat=l;

         if (tree[t].root) tree[t].root=,tree[l].root=;

         else if (tree[fa].lc==t) tree[fa].lc=l;

         else tree[fa].rc=l;

         tree[l].fat=fa;

         clean();

         maintain(t);

         maintain(l);

     }

     void splay(int t){

         while (!tree[t].root){

             int fa=tree[t].fat,gr=tree[fa].fat;

             if (tree[fa].root){

                 if (tree[fa].lc==t) right(fa);

                 else left(fa);

             }else if (tree[gr].lc==fa){

                 if (tree[fa].lc==t) right(gr),right(fa);

                 else left(fa),right(gr);

             }else if (tree[fa].rc==t) left(gr),left(fa);

             else right(fa),left(gr);

         }

     }

     void access(int t){

         xx=;

         for (int x=,y=t;y;x=y,y=tree[y].fat){

         //Wa: no(x=y)    y=fat[y];

             splay(y);

             if (x) se[y].erase(tree[x].max);

             if (tree[y].rc) se[y].insert(tree[tree[y].rc].max);

             tree[x].root=;

             tree[tree[y].rc].root=;

             // no (tree[tree[y].rc].root=1;)

             tree[y].rc=x;

             clean();

             maintain(y);

         }

     }

     int getl(int t){

         while (tree[t].lc) t=tree[t].lc;

         return t;

     }

     int getans(int t){

         access(t);

         splay(t);

         int root=getl(t);

         splay(root);

         return col[root]==col[t] ? tree[root].max : tree[tree[root].rc].max;

         //                      wa:tree[t].max

     }

     void changenum(int t,int s){

         access(t);

         splay(t);

         tree[t].t=s;

         maintain(t);

     }

     void cut(int t){

         access(t);

         splay(t);

         tree[tree[t].lc].fat=;

         tree[tree[t].lc].root=;

         tree[t].lc=;

         maintain(t);

     }

     void link(int x,int y){

         splay(x);

         access(y);

         splay(y);

         tree[x].fat=y;

         se[y].insert(tree[x].max);

         maintain(y);

     }

 }lct[];

 void dfs(int t){

     if (fat[t]) lct[col[t]].tree[t].fat=fat[t];

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t]){

         int ne=line[i].data;

         fat[ne]=t;

         dfs(ne);

         lct[col[ne]].se[t].insert(lct[col[ne]].tree[ne].max);

     }

     lct[].maintain(t);

     lct[].maintain(t);

 }

 void changecol(int t){

     if (fat[t]){

         lct[col[t]].cut(t);

         lct[col[t]^].link(t,fat[t]);

     }

     col[t]^=;

 }

 int main(){

     freopen("spoj16580.in","r",stdin);

     freopen("spoj16580.out","w",stdout);

     scanf("%d",&n);

     for (int x,y,i=;i<n;i++){

         scanf("%d%d",&x,&y);

         line[++nl]=inli(son[x],y),son[x]=nl;

         line[++nl]=inli(son[y],x),son[y]=nl;

     }

     for (int i=;i<=n;i++) scanf("%d",&col[i]);

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

         scanf("%d",&x);

         lct[].tree[i].t=lct[].tree[i].max=x;

         lct[].tree[i].t=lct[].tree[i].max=x;

     }

     dfs();

     scanf("%d",&m);

     for (int x,y,z,i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         if (i==)

         i=;

         if (x==) printf("%d\n",lct[col[y]].getans(y));

         if (x==) changecol(y);

         if (x==){

             scanf("%d",&z);

             lct[].changenum(y,z);

             lct[].changenum(y,z);

         }

     }

     fclose(stdin);

     fclose(stdout);

 }

巴特西

QTREE系列题解

最新文章

热门文章