2018-8-7 题解

发表于 2018-08-08 更新于 2020-06-11 分类于题解

lighthouse
miner
revive

lighthouse

题意

有n个人要站成一个环，有m组关系，每组关系形如u,v表示u,v不能相邻。

求有多少种方案。

两种方案不同当且仅当存在两个人在一种方案中相邻而另一种中不相邻。

题解

容斥。枚举关系的一个子集$S$，设$f_S$代表有多少种站法满足至少这S组关系不满足。

$Ans=\sum\limits_S(-1)^{|S|}f_S$。

如果这些条件恰好使得n个人站成一个环，那么$f_S=1$。

否则如果满足这些条件后出现环或者要求一个人和3个以上人相邻，显然$f_S=0$。

否则，设这些条件构成了k条链。那么$f_S=2^{k-1}(n-|S|-1)!$.

也就是说把每条链当成一个人，那么就有$(n-|S|)$个人，排列数为$\frac{(n-|S|-1)!}{2}$。然后每条链可以正着也可以反着，一共$2^k$种情况。

/*
Author: CNYALI_LK
LANG: C++
PROG: lighthouse.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
const ll p=1000000007;
ll fac[10242424],pw[192],cx[10242424],dd[1048588],fbit[1048588];
ll u[192],v[192],vis[192],cnt,fa[192],siz[192];
ll F(ll x){
    if(!cx[x])return cx[x]=++cnt;
    else return cx[x];
}
ll n,m;
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
ll orz(ll x){
    ll xcnt=-1,ycnt=0,i;
    for(ll i=1;i<=cnt;++i){vis[i]=0;fa[i]=i;siz[i]=1;}
    for(;x;){
        i=fbit[x&(-x)];
        x^=x&-x;
        ++ycnt;
        ++xcnt;
        if(vis[u[i]]==2)return 0;
        if(vis[u[i]])--xcnt;
        ++vis[u[i]];
        if(vis[v[i]]==2)return 0;
        if(vis[v[i]])--xcnt;
        ++vis[v[i]];

        if(find(u[i])==find(v[i])){return siz[find(u[i])]==n&&!x?1:0;}
        siz[find(v[i])]+=siz[find(u[i])];
        fa[find(u[i])]=find(v[i]); 
    }
    return fac[n-ycnt-1]*pw[xcnt]%p;
}
int main(){
#ifdef cnyali_lk
    freopen("lighthouse.in","r",stdin);
    freopen("lighthouse.out","w",stdout);
#endif
    n=read();m=read();
    fac[0]=pw[0]=1;
    for(ll i=1;i<=n;++i)fac[i]=fac[i-1]*i%p;
    for(ll i=1;i<=m;++i)pw[i]=pw[i-1]*2%p;
    for(ll i=0;i<m;++i){
        u[i]=F(read());
        v[i]=F(read());
    }
    ll ans=fac[n-1]*(p+1)/2%p,M=1<<m;
    dd[0]=1;
    for(ll i=0;i<m;++i)fbit[1<<i]=i;
    for(ll i=1;i<M;++i){
        dd[i]=p-dd[i^(i&(-i))];
        ans=(ans+dd[i]*orz(i))%p;
    }
    printf("%lld\n",ans);
    return 0;
}

miner

题意

有一个n点m边的无向图，选一个点当起点，每次可以进行两种操作：

0 v 走一条没走过的边到v。
1 v 瞬移到v。

你需要把每条边恰好走一遍。

求瞬移的最少次数和具体操作方案。

$n,m\le 10^5$ 可能有自环可能有重边可能不连通。

题解

就是加最少的边使得存在一条欧拉路。

首先孤立点不考虑。

对于原来的2k个奇点我们先随意连k条边使得它们不是奇点。

然后对于每个联通块跑欧拉回路。如果这个联通块中有新加的边把其中一条新加的边扔掉变成欧拉路。否则就是从它自己到它自己的欧拉路。然后把欧拉路首尾相接变成一条长的欧拉路。

/*
Author: CNYALI_LK
LANG: C++
PROG: miner.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
int e,e1;
int beg[102424],to[666667],lst[666667],deg[102424];
pii stk[666667],xans[666667];
int top,vis[102423],viss[666667];
void add(int u,int v){
    to[++e]=v;
    lst[e]=beg[u];
    beg[u]=e;
    ++deg[u];
}
void dfs(int x){
    vis[x]=1;
    int i;
    for(;beg[x];beg[x]=lst[beg[x]])if(!viss[beg[x]>>1]){
        viss[beg[x]>>1]=1;
        i=beg[x];   
        dfs(to[i]);
        stk[++top]=make_pair(to[i],i>e1);
    }
}
int main(){
#ifdef cnyali_lk
    freopen("miner.in","r",stdin);
    freopen("miner.out","w",stdout);
#endif
    int n,m,u,v;
    n=read();m=read();
    e=1;
    for(int i=1;i<=m;++i){
        add(u=read(),v=read());
        add(v,u);
    }
    e1=e;
    int oo=0;
    for(int i=1;i<=n;++i)if(deg[i]&1){
        if(oo){add(oo,i);add(i,oo); oo=0;}
        else oo=i;
    }
    int ans=0,s;
    for(int i=1;i<=n;++i)if(!vis[i]&&deg[i]){
        top=0;
        dfs(i);
        for(s=1;s<=top&&!stk[s].y;++s);
        if(s<=top){
            for(int k=0;k<top;++k){
                xans[++ans]=stk[s];     
                s=(s+top-2)%top+1;
            }
        }
        else{
            xans[++ans]=make_pair(i,1);
            for(;top;--top)xans[++ans]=stk[top];
        }
    }
    printf("%d\n%d\n",ans-1-m,xans[1].x);
    for(int i=2;i<=ans;++i)printf("%d %d\n",xans[i].y,xans[i].x);
    return 0;
}

revive

题意

给定一棵有边权的树，定义一条路径的生机值为这条路径边权和的平方。这个树的生机值定义为：对于每条路径，它的生机值的和。

先求出这棵树的生机值。

q次操作每次给一条边边权+w，求这棵树的生机值。

$n\le 10^5,q\le 5\cdot 10^5$

给出树的方式为给出每个点x的父亲$fa_x(fa_x<x)$，和边权$w_x$。

修改也是对一个点x到父亲的边边权+w。

题解

设$s_x$表示x子树的点数。

在一次对u到父亲边边权+w的操作中，考虑所有经过这条边的路径，假设一开始权值和为a。

$\sum(a+w)^2=\sum(a^2+w^2+2aw)=\sum a^2+\sum w^2+\sum 2aw$。那么生机值和增加就是$w^2s+2w\sum a$，其中s为经过这条边的路径条数也就是$s_u(n-s_u)$。

问题在于求出$a $。

对于每条$v,fa_v$的边分别考虑，有三种情况：

u是v祖先。这条边对$\sum a$的贡献为$w_vs_v(n-s_u)$。可以通过dfs序树状数组维护子树$s_vw_v$和。
v是u祖先。这条边对$\sum a$的贡献为$w_vs_u(n-s_v)$。
其它情况，这条边对$\sum a$的贡献为$s_us_vw_v$。

看上去3不太好搞，但是实际上，3可以考虑为除了这棵子树以外的v$s_us_vw_v$，那么对于v是u祖先的情况还需要加上$w_vs_u(n-2s_v)$。然后链上询问（它到根这条链）单点修改就能变成子树修改单点询问。

然后就可以3个树状数组维护了。

/*
Author: CNYALI_LK
LANG: C++
PROG: revive.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
const ll p=1000000007;
struct BIT{
    ll a[102423],n;
#define lowbit(x) (x&(-x))
    void Add(ll x,ll y){
        for(;x<=n;x+=lowbit(x))a[x]=(a[x]+y)%p; 
    }
    ll Sum(ll x){
        ll y=0;
        for(;x;x^=lowbit(x))y=(y+a[x])%p;
        return y;
    }
};
BIT a,b,c;
ll dfn[102423],t,fa[102423],w[102423],siz[102423],ans,n;
vector<ll> son[102423];
void dfs(ll x){
    dfn[x]=++t;
    siz[x]=1;
    for(auto i:son[x]){
        dfs(i);
        siz[x]+=siz[i];
    }
}
void add(ll x,ll w){
    ans=(ans+siz[x]*(n-siz[x])%p*w%p*w)%p;
    
    ans=(ans+((n-siz[x])*(a.Sum(dfn[x]+siz[x]-1)-a.Sum(dfn[x]-1)+p)%p+siz[x]*(b.Sum(dfn[x])+c.Sum(n)-c.Sum(dfn[x]+siz[x]-1)+c.Sum(dfn[x]-1)+p)%p)%p*2*w)%p;
    a.Add(dfn[x],w*siz[x]%p);
    c.Add(dfn[x],w*siz[x]%p);
    w=(n-siz[x]-siz[x]+p)*w%p;
    b.Add(dfn[x]+1,w);
    b.Add(dfn[x]+siz[x],p-w);
}
int main(){
#ifdef cnyali_lk
    freopen("revive.in","r",stdin);
    freopen("revive.out","w",stdout);
#endif
    read();
    ll q,x;
    n=read();q=read();
    a.n=b.n=c.n=n;
    for(ll i=2;i<=n;++i){
        son[fa[i]=read()].push_back(i);
        w[i]=read();
    }
    dfs(1);
    for(ll i=2;i<=n;++i)add(i,w[i]);
    printf("%lld\n",ans);
    for(;q;--q){
        x=read();add(x,read()); 
        printf("%lld\n",ans);
    }
    return 0;
}