342 D

题意

给你一个 \(3×n\) 的表格，要求放满 \(1×2\) 的多米诺骨牌，有些位置.可以放骨牌，有些位置X不能放骨牌。有一个位置O旁边至少有一个多米诺骨牌能够移动到这里（骨牌的宽对着这个格子），问有多少种方法。膜 \(10^9+7\) 。

\((3\le n\le 10^4)\)

Examples

Input

5....X.O......X.

Output

1

Input

5......O........

Output

2

Input

3........O

Output

4

解

状压dp。

对于每一列压一个状态（总共8种情况）。

关键在于怎么处理O。

方法是，暴力枚举O旁边哪些骨牌能够移到它，总共16-1=15种情况。

然后想到这15种情况中有交集，然后容斥。

具体：设 \(f(...)\) 表示哪几个方向上的骨牌能够移到它，则答案为 \(f(1)+f(2)+f(3)+f(4)-f(1,2)-f(1,3)-f(1,4)-f(2,3)-f(2,4)-f(3,4)+f(1,2,3)+f(1,2,4)+f(1,3,4)+f(2,3,4)-f(1,2,3,4)\)

Code

#include
    
     #define maxn 10003#define INF 1050000000#define mod 1000000007using namespace std;//dp[i][j]:在第i列mask中的行被覆盖，并且前i−1列被完全覆盖的放置种数int dp[maxn][8],n,no[maxn],X,Y,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};char s[3][maxn],t[3][maxn];void PE(int& x,int y){if((x+=y)>=mod)x%=mod;}void ME(int& x,int y){if((x+=mod-y)>=mod)x%=mod;}int Count(int x){int ret=0;while(x){if(x&1)ret++;x>>=1;}return ret;}int solve(){    for(int i=1;i<=n;i++){        no[i]=0;        for(int j=0;j<3;j++){            if(t[j][i]=='X'){                no[i]|=(1<
     
      2||yyy<1||yyy>n||s[xx][yy]=='X'||s[xxx][yyy]=='X'){ok=0;break;}                t[xx][yy]=t[xxx][yyy]='X';            }        }        if(!ok)continue;        int tmp=solve();        if(Count(i)&1)PE(ans,tmp);        else ME(ans,tmp);    }    printf("%d\n",ans);    return 0;}
     
    

342 E

题意

一棵树，初始时 \(1\) 号节点为红色，其他节点为蓝色，有 \(m\) 次操作：

1. 把一个蓝色节点涂成红色；
2. 询问一个节点到最近的红色节点的距离。

\((2\le n\le 10^5)\)

Examples

Input

5 4

1 2

2 3

2 4

4 5

2 1

2 5

1 2

2 5

Output

0

3

2

解 1

当红色点个数 \(\le sqrt{n}\) 时暴力查询， \(>\) 时使用一个玄学的bfs修改。

\(O(n\sqrt{n}\log n),2121ms\)

Code 1

#include
    
     #define maxn 100003#define INF 1050000000using namespace std;struct edge{    int to,next;}e[maxn<<1];int head[maxn],cnte;void add(int u,int v){    e[++cnte].to=v;    e[cnte].next=head[u];    head[u]=cnte;}int n,lg[maxn],dep[maxn],fa[maxn][23],dis[maxn],a[maxn],cnt,q[maxn],*qhead,*qtail;void init(int u,int last){    fa[u][0]=last;    for(int i=1;(1<
     
      <=dep[u];i++){        fa[u][i]=fa[fa[u][i-1]][i-1];    }    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v==last)continue;        dep[v]=dep[u]+1;        init(v,u);    }}int lca(int x,int y){    if(dep[x]
      
       dep[y]){        x=fa[x][lg[dep[x]-dep[y]]];    }    if(x==y)return x;    for(int i=lg[dep[x]];i>=0;i--){        if(fa[x][i]!=fa[y][i]){            x=fa[x][i];            y=fa[y][i];        }    }    return fa[x][0];}void bfs(){    qhead=qtail=q;    for(int i=1;i<=cnt;i++)*qtail++=a[i],dis[a[i]]=0;    while(qhead!=qtail){        int u=*qhead++;        for(int i=head[u];i;i=e[i].next){            int v=e[i].to;            if(dis[u]+1
       
        n){                bfs();                cnt=0;            }        }        else{            int ans=dis[x];            for(int i=1;i<=cnt;i++){                ans=min(ans,dep[x]+dep[a[i]]-(dep[lca(x,a[i])]<<1));            }            printf("%d\n",ans);        }    }    return 0;}
       
      
     
    

解 2

将 \(\log\) 的lca查询改为在欧拉序上用ST表 \(O(1)\) 查询。

\(O(n\sqrt{n}),312ms\)

Code 2

#include
    
     #define maxn 100003#define INF 1050000000using namespace std;struct edge{    int to,next;}e[maxn<<1];int head[maxn],cnte;void add(int u,int v){    e[++cnte].to=v;    e[cnte].next=head[u];    head[u]=cnte;}int n,dep[maxn],lg[maxn<<1],st[maxn<<1][23],dfn[maxn],cntdfn,dis[maxn],a[maxn],cnt,q[maxn],*qhead,*qtail;void init(int u,int last){    st[++cntdfn][0]=u;    dfn[u]=cntdfn;    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v==last)continue;        dep[v]=dep[u]+1;        init(v,u);        st[++cntdfn][0]=u;    }}int work(int x,int y){return dep[x]
     
      dfn[y])swap(x,y);    int tmp=lg[dfn[y]-dfn[x]+1];    return work(st[dfn[x]][tmp],st[dfn[y]-(1<
      
       n){                bfs();                cnt=0;            }        }        else{            int ans=dis[x];            for(int i=1;i<=cnt;i++){                ans=min(ans,dep[x]+dep[a[i]]-(dep[lca(x,a[i])]<<1));            }            printf("%d\n",ans);        }    }    return 0;}
      
     
    

解 3

树链剖分，开的线段树上每个节点维护两个值：最近红色节点到链顶端的距离 \(U\) ；最近红色节点到链底端的距离 \(D\) 。

询问时每次跳到一个节点，就在线段树里询问链顶端到当前节点的 \(D\) 值和链底端到当前节点的 \(U\) 值。

Code 3

#include
    
     #define maxn 100003#define INF 1050000000using namespace std;struct edge{    int from,to,next;}e[maxn<<1];int head[maxn],cnte;void add(int u,int v){    e[++cnte].to=v;    e[cnte].from=u;    e[cnte].next=head[u];    head[u]=cnte;}int n,fa[maxn],son[maxn],dep[maxn],sz[maxn],dfn[maxn],num[maxn],rig[maxn],cntdfn,top[maxn],cntli[maxn],numli[maxn],dis[maxn];namespace SEG{    struct node{        int disup,disdown;        node():disup(INF),disdown(INF){}    }t[maxn<<2];    void pushup(node& t1,const node& t2,const node& t3){        t1.disup=min(t2.disup,t3.disup);        t1.disdown=min(t2.disdown,t3.disdown);    }    void change(int p,int l,int r,int pos,int u){        if(l==r){            t[p].disup=dis[u]+numli[u];            t[p].disdown=dis[u]+cntli[top[u]]-numli[u]-1;            return;        }        int mid=(l+r)>>1;        if(pos<=mid)change(p<<1,l,mid,pos,u);        else change(p<<1|1,mid+1,r,pos,u);        pushup(t[p],t[p<<1],t[p<<1|1]);    }    int query(int p,int l,int r,int seg_l,int seg_r,bool up){        if(seg_l<=l&&r<=seg_r){            return up?t[p].disup:t[p].disdown;        }        int mid=(l+r)>>1,ret=INF;        if(seg_l<=mid)ret=min(ret,query(p<<1,l,mid,seg_l,seg_r,up));        if(seg_r>mid)ret=min(ret,query(p<<1|1,mid+1,r,seg_l,seg_r,up));        return ret;    }}void initdep(int u,int last){    fa[u]=last;    sz[u]=1;    int mxsz=0;    for(int i=head[u];i;i=e[i].next){        int v=e[i].to;        if(v==fa[u])continue;        dep[v]=dep[u]+1;        initdep(v,u);        sz[u]+=sz[v];        if(sz[v]>mxsz)mxsz=sz[v],son[u]=v;    }}void initdfn(int u,int tp){    dfn[u]=++cntdfn;    num[cntdfn]=u;    top[u]=tp;    numli[u]=cntli[tp];    cntli[tp]++;    if(son[u]){        initdfn(son[u],tp);        for(int i=head[u];i;i=e[i].next){            int v=e[i].to;            if(v==fa[u]||v==son[u])continue;            initdfn(v,v);        }    }    rig[u]=cntdfn;}void change(int u){    for(int v=u;v;v=fa[top[v]]){        if(dep[u]-dep[v]