题解归档 - cf2236G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2236G
• 本地来源：problems/cf2236G/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/G

思路

pattern:
path query monoid / HLD
claim:
For nonnegative integers, sum >= xor always. Therefore a subsegment is hospitable iff sum == xor, i.e. no bit appears in two different elements of that subsegment.
why:
Binary addition can only add carries, so sum is xor plus nonnegative carry contributions. Equality means every bit column has at most one 1.
monoid:
For an ordered sequence keep:

• ans: number of valid nonempty subsegments inside it.
• valid prefixes compressed by OR mask and count.
• valid suffixes compressed by OR mask and count.
• whether the whole sequence is valid and its OR mask.

To merge A+B, add internal answers and every suffix/prefix pair whose masks are disjoint. Prefixes and suffixes extend across the boundary only when the whole opposite side is valid and masks are disjoint. A valid prefix/suffix has at most 20 nonzero-bit additions, so the mask lists stay small.
tree:
Use HLD. Segment tree nodes store the monoid in top-down order. For an upward chain piece, reverse the summary by swapping prefix and suffix lists. A path query merges pieces in exact path order.
check:
Use brute.cpp for small trees: materialize each path, enumerate all subsegments, and compare with the HLD monoid solution.
edge:
Zero has mask 0, so it can be included with any valid segment and many prefixes/suffixes may share mask 0; counts must be aggregated per mask.

代码

来源：problems/cf2236G/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100005;
const int maxlog=20;
const int maxe=200005;
const int segmax=1<<18;
const int lim=22;
struct node{
    int len,fullMask,pc,sc;
    ll ans;
    bool full;
    int pm[lim],sm[lim];
    ll pv[lim],sv[lim];
};
int n,q,tot,tsz;
int a[maxn],head[maxn],to[maxe],nxt[maxe];
int fa[maxn],dep[maxn],sz[maxn],heavy[maxn],top[maxn],pos[maxn],who[maxn];
node seg[segmax+5];
void addEdge(int u,int v){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
node emptyNode(){
    node x;
    x.len=0;
    x.fullMask=0;
    x.pc=x.sc=0;
    x.ans=0;
    x.full=true;
    return x;
}
node singleNode(int v){
    node x=emptyNode();
    x.len=1;
    x.ans=1;
    x.full=true;
    x.fullMask=v;
    x.pc=x.sc=1;
    x.pm[0]=x.sm[0]=v;
    x.pv[0]=x.sv[0]=1;
    return x;
}
void addPair(int m,ll c,int *ms,ll *cs,int &cnt){
    for(int i=0;i<cnt;i++){
        if(ms[i]==m){
            cs[i]+=c;
            return;
        }
    }
    ms[cnt]=m;
    cs[cnt]=c;
    cnt++;
}
node revNode(node x){
    swap(x.pc,x.sc);
    for(int i=0;i<lim;i++){
        swap(x.pm[i],x.sm[i]);
        swap(x.pv[i],x.sv[i]);
    }
    return x;
}
node mergeNode(const node &A,const node &B){
    if(!A.len) return B;
    if(!B.len) return A;
    node C=emptyNode();
    C.len=A.len+B.len;
    C.ans=A.ans+B.ans;
    for(int i=0;i<A.sc;i++){
        for(int j=0;j<B.pc;j++){
            if((A.sm[i]&B.pm[j])==0) C.ans+=A.sv[i]*B.pv[j];
        }
    }
    C.full=A.full&&B.full&&((A.fullMask&B.fullMask)==0);
    C.fullMask=C.full?(A.fullMask|B.fullMask):0;
    for(int i=0;i<A.pc;i++) addPair(A.pm[i],A.pv[i],C.pm,C.pv,C.pc);
    if(A.full){
        for(int i=0;i<B.pc;i++){
            if((A.fullMask&B.pm[i])==0) addPair(A.fullMask|B.pm[i],B.pv[i],C.pm,C.pv,C.pc);
        }
    }
    for(int i=0;i<B.sc;i++) addPair(B.sm[i],B.sv[i],C.sm,C.sv,C.sc);
    if(B.full){
        for(int i=0;i<A.sc;i++){
            if((A.sm[i]&B.fullMask)==0) addPair(A.sm[i]|B.fullMask,A.sv[i],C.sm,C.sv,C.sc);
        }
    }
    return C;
}
void buildSeg(){
    tsz=1;
    while(tsz<n) tsz<<=1;
    for(int i=1;i<2*tsz;i++) seg[i]=emptyNode();
    for(int i=1;i<=n;i++) seg[tsz+i-1]=singleNode(a[who[i]]);
    for(int i=tsz-1;i>=1;i--) seg[i]=mergeNode(seg[i<<1],seg[i<<1|1]);
}
node querySeg(int l,int r){
    node L=emptyNode(),R=emptyNode();
    l+=tsz-1;
    r+=tsz-1;
    while(l<=r){
        if(l&1) L=mergeNode(L,seg[l++]);
        if(!(r&1)) R=mergeNode(seg[r--],R);
        l>>=1;
        r>>=1;
    }
    return mergeNode(L,R);
}
void buildHld(){
    vector<int>ord;
    ord.reserve(n);
    ord.push_back(1);
    fa[1]=0;
    dep[1]=0;
    for(int qi=0;qi<(int)ord.size();qi++){
        int u=ord[qi];
        for(int e=head[u];e;e=nxt[e]){
            int v=to[e];
            if(v==fa[u]) continue;
            fa[v]=u;
            dep[v]=dep[u]+1;
            ord.push_back(v);
        }
    }
    for(int i=n-1;i>=0;i--){
        int u=ord[i];
        sz[u]=1;
        heavy[u]=0;
        for(int e=head[u];e;e=nxt[e]){
            int v=to[e];
            if(v==fa[u]) continue;
            sz[u]+=sz[v];
            if(!heavy[u] or sz[v]>sz[heavy[u]]) heavy[u]=v;
        }
    }
    int timer=0;
    vector<pair<int,int>>st;
    st.push_back({1,1});
    while(!st.empty()){
        auto [u,tp]=st.back();
        st.pop_back();
        for(int x=u;x;x=heavy[x]){
            top[x]=tp;
            pos[x]=++timer;
            who[timer]=x;
            for(int e=head[x];e;e=nxt[e]){
                int v=to[e];
                if(v==fa[x] or v==heavy[x]) continue;
                st.push_back({v,v});
            }
        }
    }
}
node queryPath(int u,int v){
    node up=emptyNode(),down=emptyNode();
    while(top[u]!=top[v]){
        if(dep[top[u]]>=dep[top[v]]){
            node cur=querySeg(pos[top[u]],pos[u]);
            up=mergeNode(up,revNode(cur));
            u=fa[top[u]];
        }else{
            node cur=querySeg(pos[top[v]],pos[v]);
            down=mergeNode(cur,down);
            v=fa[top[v]];
        }
    }
    if(dep[u]>=dep[v]){
        node cur=querySeg(pos[v],pos[u]);
        up=mergeNode(up,revNode(cur));
    }else{
        node cur=querySeg(pos[u],pos[v]);
        down=mergeNode(cur,down);
    }
    return mergeNode(up,down);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        tot=0;
        for(int i=1;i<=n;i++) head[i]=0;
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            addEdge(u,v);
            addEdge(v,u);
        }
        buildHld();
        buildSeg();
        while(q--){
            int u,v;
            scanf("%d%d",&u,&v);
            printf("%lld\n",queryPath(u,v).ans);
        }
    }
    return 0;
}