http://acm.hdu.edu.cn/showproblem.php?pid=4897

?

題意：
給你一棵樹,邊的顏色要么為白色，要么為黑色，初始每條邊為白色,有三種操作

1、將u-v鏈上面的所有邊的顏色翻轉(zhuǎn) 2、將u-v鏈上面所有鄰接的邊翻轉(zhuǎn)(邊上只有一個(gè)點(diǎn)在鏈上面) 3、詢問u->v上面有多少黑色的邊

?

樹鏈剖分，線段樹維護(hù)4個(gè)信息：

按dfs序建立線段樹后，如果線段樹內(nèi)節(jié)點(diǎn)的區(qū)間為[l,r]，則此節(jié)點(diǎn)維護(hù)樹上dfs序[l,r]內(nèi)的父邊的信息

父邊指 點(diǎn)與父節(jié)點(diǎn)之間的邊

sum0：節(jié)點(diǎn)的父邊屬于重鏈且顏色為白色 的邊數(shù)

sum1：節(jié)點(diǎn)的父邊屬于重鏈且顏色為黑色 的邊數(shù)

rev1：節(jié)點(diǎn)的父邊顏色是否被操作1取反 （實(shí)際只會(huì)用到屬于輕鏈的邊）

rev2：節(jié)點(diǎn)的子樹中，與節(jié)點(diǎn)直接相連的屬于輕鏈邊 是否被操作2取反

?

操作1：直接取反，交換sum0和sum1，維護(hù)標(biāo)記rev1

細(xì)節(jié)：最后u和v（dep[u]<dep[v]）匯集到一條重鏈的時(shí)候，最后一次操作不包括u，因?yàn)辄c(diǎn)代表的是父邊的信息

?

操作2：一條鏈的相鄰邊，除了對(duì)鏈上的點(diǎn)維護(hù)rev2操作外，

鏈最頂端的點(diǎn)如果是其父節(jié)點(diǎn)的重兒子，需要修改它的rev1

路徑上每條重鏈最底端的點(diǎn)，如果它有重兒子，需要修改它重兒子的rev1

因?yàn)闃?biāo)記rev2只維護(hù)輕鏈

?

操作3：重鏈直接查，輕鏈呢？

在樹鏈剖分往上跳的時(shí)候，跳輕鏈一定是只跳一條邊

假設(shè)這條邊連接了節(jié)點(diǎn)u和v，dep[u]<dep[v]

如果rev2[u]^rev2[v]^rev1[v] 為 true，則這條邊為黑色

?

clj的題就是好哇！！！

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;#define N 100001int n;int front[N],nxt[N<<1],to[N<<1],tot;int siz[N],dep[N],fa[N]; int bl[N],son[N]; int id[N],dy[N],cnt;bool big[N];int sum0[N<<2],sum1[N<<2]; bool rev1[N<<2],rev2[N<<2];int ans;void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void add(int u,int v) {to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; }void dfs1(int x) {siz[x]=1;for(int i=front[x];i;i=nxt[i])if(to[i]!=fa[x]){fa[to[i]]=x;dep[to[i]]=dep[x]+1;dfs1(to[i]);siz[x]+=siz[to[i]];} }void dfs2(int x,int top) {bl[x]=top;id[x]=++cnt;dy[cnt]=x;int y=0;for(int i=front[x];i;i=nxt[i])if(to[i]!=fa[x] && siz[to[i]]>siz[y]) y=to[i];if(y) {son[x]=y;big[y]=true;dfs2(y,top);}else return;for(int i=front[x];i;i=nxt[i])if(to[i]!=fa[x] && to[i]!=y) dfs2(to[i],to[i]); }void down1(int k) {rev1[k<<1]^=1;swap(sum0[k<<1],sum1[k<<1]);rev1[k<<1|1]^=1;swap(sum0[k<<1|1],sum1[k<<1|1]);rev1[k]^=1; }void down2(int k) {rev2[k<<1]^=1;rev2[k<<1|1]^=1;rev2[k]^=1; }void Reverse(int k,int l,int r,int opl,int opr,int ty) {if(l>=opl && r<=opr){if(ty==1){swap(sum1[k],sum0[k]);rev1[k]^=1;}else rev2[k]^=1;return;}int mid=l+r>>1;if(rev1[k]) down1(k);if(rev2[k]) down2(k);if(opl<=mid) Reverse(k<<1,l,mid,opl,opr,ty);if(opr>mid) Reverse(k<<1|1,mid+1,r,opl,opr,ty);if(ty==1){sum1[k]=sum1[k<<1]+sum1[k<<1|1];sum0[k]=sum0[k<<1]+sum0[k<<1|1];} }int get_lca(int u,int v) {while(bl[u]!=bl[v]){if(dep[bl[u]]<dep[bl[v]]) swap(u,v);u=fa[bl[u]];}return dep[u]<dep[v] ? u : v; }bool point_query(int k,int l,int r,int x,int ty) {if(l==r) return ty==1 ? rev1[k] : rev2[k];if(rev1[k]) down1(k);if(rev2[k]) down2(k);int mid=l+r>>1;if(x<=mid) return point_query(k<<1,l,mid,x,ty);return point_query(k<<1|1,mid+1,r,x,ty); }void query(int k,int l,int r,int opl,int opr) {if(l>=opl && r<=opr){ans+=sum1[k];return;}if(rev1[k]) down1(k);if(rev2[k]) down2(k);int mid=l+r>>1;if(opl<=mid) query(k<<1,l,mid,opl,opr);if(opr>mid) query(k<<1|1,mid+1,r,opl,opr); }void solve(int ty,int u,int v) {if(ty==1){while(bl[u]!=bl[v]){if(dep[bl[u]]<dep[bl[v]]) swap(u,v);Reverse(1,1,n,id[bl[u]],id[u],1);u=fa[bl[u]];}if(dep[u]>dep[v]) swap(u,v);if(u!=v) Reverse(1,1,n,id[u]+1,id[v],1);}else if(ty==2){int lca=get_lca(u,v);if(lca!=u && lca!=v) {if(big[lca]) Reverse(1,1,n,id[lca],id[lca],1);}else{if(dep[u]>dep[v]) swap(u,v);if(big[u]) Reverse(1,1,n,id[u],id[u],1);}while(bl[u]!=bl[v]){if(dep[bl[u]]<dep[bl[v]]) swap(u,v);if(son[u]) Reverse(1,1,n,id[son[u]],id[son[u]],1);Reverse(1,1,n,id[bl[u]],id[u],2);u=fa[bl[u]];}if(dep[u]>dep[v]) swap(u,v); if(son[v]) Reverse(1,1,n,id[son[v]],id[son[v]],1);Reverse(1,1,n,id[u],id[v],2);}else{ ans=0; while(bl[u]!=bl[v]){if(dep[bl[u]]<dep[bl[v]]) swap(u,v);query(1,1,n,id[bl[u]],id[u]);ans+=point_query(1,1,n,id[bl[u]],2)^point_query(1,1,n,id[fa[bl[u]]],2)^point_query(1,1,n,id[bl[u]],1);u=fa[bl[u]];}if(dep[u]>dep[v]) swap(u,v);if(u!=v) query(1,1,n,id[u]+1,id[v]);printf("%d\n",ans);} } void build(int k,int l,int r) {sum0[k]=sum1[k]=0;rev1[k]=rev2[k]=false;if(l==r) {sum0[k]=big[dy[l]];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);sum0[k]=sum0[k<<1]+sum0[k<<1|1]; }void clear() {tot=cnt=0;memset(front,0,sizeof(front));memset(son,0,sizeof(son));memset(big,false,sizeof(big)); }int main() {freopen("data.in","r",stdin);freopen("my.out","w",stdout);int T;read(T);int u,v;int ty,m,lca;while(T--){clear();read(n);for(int i=1;i<n;++i){read(u); read(v);add(u,v);}dfs1(1);dfs2(1,1);build(1,1,n);read(m);while(m--){read(ty); read(u); read(v);solve(ty,u,v);}}return 0; }

?

Little Devil I

Time Limit: 16000/8000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1087????Accepted Submission(s): 378

Problem Description There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli.

The devil likes to make thing in chaos. This kingdom’s road system is like simply a tree(connected graph without cycle). A road has a color of black or white. The devil often wants to make some change of this system.

In details, we call a path on the tree from a to b consists of vertices lie on the shortest simple path between a and b. And we say an edge is on the path if both its two endpoints is in the path, and an edge is adjacent to the path if exactly one endpoint of it is in the path.

Sometimes the devil will ask you to reverse every edge’s color on a path or adjacent to a path.

The king’s daughter, WJMZBMR, is also a cute loli, she is surprised by her father’s lolicon-like behavior. As she is concerned about the road-system’s status, sometimes she will ask you to tell there is how many black edge on a path.

Initially, every edges is white.

?

Input The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains an integer n, which is the size of the tree. The vertices be indexed from 1.
On the next n-1 lines, each line contains two integers a,b, denoting there is an edge between a and b.
The next line contains an integer Q, denoting the number of the operations.
On the next Q lines, each line contains three integers t,a,b. t=1 means we reverse every edge’s color on path a to b. t=2 means we reverse every edge’s color adjacent to path a to b. t=3 means we query about the number of black edge on path a to b.

T<=5.
n,Q<=10^5.
Please use scanf,printf instead of cin,cout,because of huge input.

?

Output For each t=3 operation, output the answer in one line.

?

Sample Input 1 10 2 1 3 1 4 1 5 1 6 5 7 4 8 3 9 5 10 6 10 2 1 6 1 3 8 3 8 10 2 3 4 2 10 8 2 4 10 1 7 6 2 7 3 2 1 4 2 10 10

?

Sample Output 3 Hint reverse color means change from white to black or vice virsa.

?

Author WJMZBMR

轉(zhuǎn)載于:https://www.cnblogs.com/TheRoadToTheGold/p/8456845.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的hdu 4857 Little Devil I的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。