HDU 4897 Little Devil I-白红宇

HDU 4897 Little Devil I

阅读量：5150 次

发布时间：2019-06-13

本文共 4637 字，大约阅读时间需要 15 分钟。

题面：从前有一个国家，国家里面的城市是树形结构的。这个国家的国王是个萝莉控，爱上了一个小恶魔。

小恶魔喜欢制造混乱，经常让国王修改城市之间的道路系统。每条道路有两种颜色，黑与白。

修改有两种，一是把城市a和b之间的道路全部翻转颜色，二是把城市a和b之间道路的相邻路翻色。

国王的萝莉女儿，WJMZBMR很关心国家道路状况，她会询问a和b之间的道路有多少是黑色的。

一开始所有道路都是白色。

分析：

第一种操作就是最简单的树链剖分。

第二种操作如果要用树链剖分，需要仔细思考。

首先，还是只能更新那logN条链，可以想到在链上打标记来表示更新了周围的点。这样做是否可行呢？

在路径的重链上，中间的点是不变的，被标记了两次，这是合法的。

考虑询问。在询问的时候，存在两个问题，1.重链的点很多，2.某个点的度数很多。这将导致复杂度变成O(n)。

需要修改标记的含义，对于2，一条边只需要一个标记的点就够了，最适合的点是这条边的父结点。

对于1，重链上中间的点是不必标记的。

综上，在一个父节点打标记表示修改了它的孩子轻边。剩下O(logN)个端点特殊处理一下，复杂不会退化。

标记区间更新点，翻转区间更新边，这个操作可以用线段树完成。（边的id用它的子结点编号，这个写着的时候挺容易出错的。

复杂度O(Qlognlogn)

/**********************************************************            ------------------                          **   author AbyssFish                                     ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;const int maxn = 1e5+5;int hd[maxn], nx[maxn<<1], to[maxn<<1], ec;void add_edge(int u,int v){ nx[ec] = hd[u]; to[ec] = v; hd[u] = ec++;}void init_g(int n){ memset(hd+1,0xff,n*sizeof(int)); ec = 0; }#define eachedge int i = hd[u]; ~i; i = nx[i]#define ifvalid int v = to[i]; if(v == fa[u]) continue;int n;/*----------------------------------------*/int fa[maxn];int tr_sz[maxn];int top[maxn];int son[maxn];int dep[maxn];int id[maxn];int id_cnt;// id[0] = tr_sz[0] = 0void dfs(int u,int f = 0,int d = 0){ dep[u] = d; son[u] = 0; fa[u] = f; tr_sz[u] = 1; for(eachedge){ ifvalid dfs(v,u,d+1); tr_sz[u] += tr_sz[v]; if(tr_sz[v] > tr_sz[son[u]]){ son[u] = v; } }}void sub_dv(int u,int tp){ top[u] = tp; id[u] = ++id_cnt; if(son[u]) sub_dv(son[u],tp); for(eachedge){ ifvalid if(v != son[u]) sub_dv(v,v); }}/*----------------------------------------*/#define para int o = 1,int l = 1,int r = n#define lo (o<<1)#define ro (o<<1|1)#define Tvar int md = (l+r)>>1;#define lsn lo,l,md#define rsn ro,md+1,r#define insd ql<=l&&r<=qr#define qpara int ql,int qr,para#define qlsn ql, qr,lsn#define qrsn ql, qr,rsnconst int ST_SIZE = 1<<18;int flp[ST_SIZE], sum[ST_SIZE]; //edgeint flg[ST_SIZE];//vertexvoid build(para){ sum[o] = flp[o] = flg[o] = 0; if(l < r){ Tvar build(lsn); build(rsn); }}inline void sink(int o,int tot){ flp[o] ^= 1; sum[o] = tot - sum[o];}inline void dwn_flp(int o,int l,int r){ if(flp[o]){ Tvar sink(lo,md+1-l); sink(ro,r-md); flp[o] = 0; }}void update_flp(qpara){ if(insd){ sink(o,r+1-l); } else { Tvar dwn_flp(o,l,r); if(ql <= md) update_flp(qlsn); if(qr > md) update_flp(qrsn); sum[o] = sum[lo] + sum[ro]; }}int q_flp_sum(qpara){ if(insd) return sum[o]; else { Tvar dwn_flp(o,l,r); int re = 0; if(ql <= md) re += q_flp_sum(qlsn); if(qr > md) re += q_flp_sum(qrsn); return re; }}/*----------------------------------------*/int q_flg(int qpos, para){ if(l == r) return flg[o]; else { Tvar return flg[o]^(qpos <= md ? q_flg(qpos,lsn) : q_flg(qpos,rsn)); }}void update_flg(qpara){ if(insd) flg[o] ^= 1; else { Tvar if(ql <= md) update_flg(qlsn); if(qr > md) update_flg(qrsn); }}/*----------------------------------------*/void rvPath(int a,int b){ int p = top[a], q = top[b]; while(p != q){ if(dep[p] < dep[q]) swap(a,b), swap(p,q); update_flp(id[p],id[a]); p = top[a = fa[p]]; } if(a != b){ if(dep[a] > dep[b]) swap(a,b); update_flp(id[son[a]],id[b]); }}void rvAdj(int a,int b){ int p = top[a], q = top[b]; while(p != q){ if(dep[p] < dep[q]) swap(a,b), swap(p,q); update_flg(id[p],id[a]); update_flp(id[p],id[p]); if(son[a]) { update_flp(id[son[a]],id[son[a]]); } p = top[a = fa[p]]; } if(dep[a] > dep[b]) swap(a,b); update_flg(id[a],id[b]); update_flp(id[a],id[a]); if(son[b]) { update_flp(id[son[b]],id[son[b]]); }}int query(int a,int b){ int re = 0; int p = top[a], q = top[b]; while(p != q){ if(dep[p] < dep[q]) swap(a,b), swap(p,q); if(a != p){ re += q_flp_sum(id[son[p]],id[a]); } re += q_flg(id[fa[p]]) ^ q_flp_sum(id[p],id[p]); p = top[a = fa[p]]; } if(a != b){ if(dep[a] > dep[b]) swap(a,b); re += q_flp_sum(id[son[a]],id[b]); } return re;}/*----------------------------------------*/void init(){ scanf("%d",&n); init_g(n); int a,b; for(int i = 1; i < n; i++){ scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); }}void solve(){ id_cnt = 0; dfs(1); sub_dv(1,1); build(); int Q; scanf("%d",&Q); int t,a,b; while(Q--){ scanf("%d%d%d",&t,&a,&b); if(t == 1) rvPath(a,b); else if(t == 2) rvAdj(a,b); else if(t == 3) printf("%d\n", query(a,b)); }}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif //cout<