HDU 5614 Baby Ming and Matrix tree (树链剖分)

本文主要是介绍HDU 5614 Baby Ming and Matrix tree (树链剖分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

一颗树上，树上每个点是一个2×2的01矩阵（每个矩阵有两个1和两个0），可以顺时针旋转这个矩阵旧时度（代价2），或者直接替换（代价10），每次给你一个v,u和一个矩阵，问v到u的路上的矩阵全部变成刚给的矩阵的最小代价

思路：

树链剖分，因为1有两个，所以只有6种矩阵（其中又可以分成两组，每组中的矩阵可以相互转换），那么我们把矩阵手动手动标号，算出转换最小代价，然后用6棵线段树暴力查询，每次查询的时候用lazy染色即可

错误及反思：

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N =20100;int segtree[N*4][8],lazy[N*4];
int matrix[N][4],bh[N];
struct EDGE{int to,next;
}e[N*2];int tot,tid,n,q;
int top[N],si[N],fa[N],first[N],son[N],depth[N],id[N],rnk[N];int getid(int a,int b,int c,int d){if(a==1&&b==1&&c==0&&d==0) return 1;if(a==0&&b==1&&c==0&&d==1) return 2;if(a==0&&b==0&&c==1&&d==1) return 3;if(a==1&&b==0&&c==1&&d==0) return 4;if(a==0&&b==1&&c==1&&d==0) return 5;if(a==1&&b==0&&c==0&&d==1) return 6;
}
void addedge(int x,int y){e[tot].to=y;e[tot].next=first[x];first[x]=tot++;e[tot].to=x;e[tot].next=first[y];first[y]=tot++;
}void dfs1(int now,int bef,int dep){fa[now]=bef;depth[now]=dep;si[now]=1;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=bef){dfs1(e[i].to,now,dep+1);si[now]+=si[e[i].to];if(son[now]==-1) son[now]=e[i].to;else son[now]=si[e[i].to]>si[son[now]]?e[i].to:son[now];}
}void dfs2(int now,int tp){top[now]=tp;id[now]=tid++;if(son[now]!=-1) dfs2(son[now],tp);for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=fa[now]&&e[i].to!=son[now])dfs2(e[i].to,e[i].to);
}void init(){memset(segtree,0,sizeof(segtree));memset(lazy,0,sizeof(lazy));tot=0; tid=1;memset(first,-1,sizeof(first));memset(son,-1,sizeof(son));
}
void pushup(int l,int r,int rt)
{for(int i=1;i<=6;i++)segtree[rt][i]=segtree[rt<<1][i]+segtree[rt<<1|1][i];
}
void build(int l,int r,int rt){if(l==r){segtree[rt][bh[rnk[l]]]++;return ;}int m=(l+r)/2;build(lson);build(rson);pushup(l,r,rt);return ;
}void pushdown(int l,int r,int rt){if(lazy[rt]){for(int i=1;i<=6;i++)segtree[rt<<1][i]=0;for(int i=1;i<=6;i++)segtree[rt<<1|1][i]=0;int m=(l+r)/2;segtree[rt<<1][lazy[rt]]=m-l+1;segtree[rt<<1|1][lazy[rt]]=r-m;lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];lazy[rt]=0;}
}int query(int tx,int L,int R,int l,int r,int rt){int ans=0;if(L<=l&&R>=r){if(tx==1) ans+=segtree[rt][2]*6+segtree[rt][3]*4+segtree[rt][4]*2+segtree[rt][5]*10+segtree[rt][6]*10;if(tx==2) ans+=segtree[rt][1]*2+segtree[rt][3]*6+segtree[rt][4]*4+segtree[rt][5]*10+segtree[rt][6]*10;if(tx==3) ans+=segtree[rt][2]*2+segtree[rt][4]*6+segtree[rt][1]*4+segtree[rt][5]*10+segtree[rt][6]*10;if(tx==4) ans+=segtree[rt][1]*6+segtree[rt][3]*2+segtree[rt][2]*4+segtree[rt][5]*10+segtree[rt][6]*10;if(tx==5) ans+=segtree[rt][1]*10+segtree[rt][2]*10+segtree[rt][3]*10+segtree[rt][4]*10+segtree[rt][6]*2;if(tx==6) ans+=segtree[rt][1]*10+segtree[rt][2]*10+segtree[rt][3]*10+segtree[rt][4]*10+segtree[rt][5]*2;for(int i=1;i<=6;i++)segtree[rt][i]=0;lazy[rt]=tx;segtree[rt][tx]=r-l+1;return ans;}pushdown(l,r,rt);int m=(l+r)/2;if(L<=m) ans+=query(tx,L,R,lson);if(R>m) ans+=query(tx,L,R,rson);pushup(l,r,rt);return ans;
}int modify(int tx,int L,int R){int f1=top[L],f2=top[R];int ans=0;while(f1!=f2){if(depth[f1]<depth[f2]){swap(f1,f2);swap(L,R);}ans+=query(tx,id[f1],id[L],1,tid-1,1);L=fa[f1];f1=top[L];}if(depth[L]>depth[R]) swap(L,R);ans+=query(tx,id[L],id[R],1,tid-1,1);return ans;
}int main(){int T;scanf("%d",&T);while(T--){init();scanf("%d",&n);for(int i=0,u,v;i<n-1;i++){scanf("%d%d",&u,&v);addedge(u,v);}dfs1(1,1,1);dfs2(1,1);for(int i=1;i<=n;i++)rnk[id[i]]=i;for(int i=1;i<=n;i++){int ta,tb,tc,td;scanf("%1d%1d%1d%1d",&ta,&tb,&tc,&td);bh[i]=getid(ta,tb,tc,td);}build(1,n,1);scanf("%d",&q);while(q--){int la,lb;scanf("%d%d",&la,&lb);int ta,tb,tc,td;scanf("%1d%1d%1d%1d",&ta,&tb,&tc,&td);int tx=getid(ta,tb,tc,td);printf("%d\n",modify(tx,la,lb));}}
}