12.21
鲜花
做题纪要
LibreOJ 121. 「离线可过」动态图连通性
-
线段树分治板子。
点击查看代码
int u[500010],v[500010],w[500010],st[500010],ed[500010],ans[500010]; pair<int,int>e[500010]; map<pair<int,int>,int>f; struct quality { int id,fa,siz; }; struct DSU { int fa[500010],siz[500010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; siz[i]=1; } } int find(int x) { return fa[x]==x?x:find(fa[x]); } void merge(int x,int y,stack<quality>&s) { x=find(x); y=find(y); if(x!=y) { s.push((quality){x,fa[x],siz[x]}); s.push((quality){y,fa[y],siz[y]}); if(siz[x]<siz[y]) { swap(x,y); } fa[y]=x; siz[x]+=siz[y]; } } void split(stack<quality>&s) { while(s.empty()==0) { fa[s.top().id]=s.top().fa; siz[s.top().id]=s.top().siz; s.pop(); } } }D; struct SMT { struct SegmentTree { vector<int>info; }tree[2000010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void update(int rt,int l,int r,int x,int y,int id) { if(x<=l&&r<=y) { tree[rt].info.push_back(id); return; } int mid=(l+r)/2; if(x<=mid) { update(lson(rt),l,mid,x,y,id); } if(y>mid) { update(rson(rt),mid+1,r,x,y,id); } } void solve(int rt,int l,int r) { stack<quality>s; int mid=(l+r)/2; for(int i=0;i<tree[rt].info.size();i++) { D.merge(u[tree[rt].info[i]],v[tree[rt].info[i]],s); } if(l==r) { ans[l]=(D.find(e[l].first)==D.find(e[l].second)); } else { solve(lson(rt),l,mid); solve(rson(rt),mid+1,r); } D.split(s); } }T; int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,m=0,q,pd,tim=0,x,y,i; cin>>n>>q; for(i=1;i<=q;i++) { cin>>pd; if(pd==0) { m++; cin>>u[m]>>v[m]; f[make_pair(u[m],v[m])]=f[make_pair(v[m],u[m])]=m; st[m]=tim+1; ed[m]=-1; } if(pd==1) { cin>>x>>y; ed[f[make_pair(x,y)]]=tim; } if(pd==2) { tim++; cin>>e[tim].first>>e[tim].second; } } if(tim!=0) { for(i=1;i<=m;i++) { ed[i]=(ed[i]==-1)?tim:ed[i]; if(st[i]<=ed[i]) { T.update(1,1,tim,st[i],ed[i],i); } } D.init(n); T.solve(1,1,tim); for(i=1;i<=tim;i++) { cout<<(ans[i]==1?"Y":"N")<<endl; } } return 0; }
luogu P11363 [NOIP2024] 树的遍历
-
观察到遍历边的过程实际上是第一次到达 \(x\) 后对于剩下的 \(du_{x}-1\) 条边以一条链的形式走完，中途可能会有其他的边加入但不影响这条链上只有这 \(du_{x}-1\) 条边。故可以得到 \(k=1\) 时答案为 \(\prod\limits_{i=1}^{n}(du_{i}-1)!\) 。
-
同时发现若两条边均可以作为同一棵新树的根节点，那么原树上这两条边之间的所有边都可以作为根节点生成这棵新树。
-
对于一个由关键边组成的边集，若存在一棵新树使其集合中的边均能作为这棵新树上的根节点，则有这些关键边在原树上必然能形成一条链。
-
设 \(g_{i}\) 表示所有链上有 \(i\) 条关键边的链（链头和链尾必须都是关键边）能构成多少棵新树，容斥完有 \(\sum\limits_{i=1}^{k}(-1)^{i+1}g_{i}\) 即为所求。
-
对于一条有 \(l\) 条关键边的链 \(S\) ，其对 \(g_{k}\) 的贡献为 \(\dbinom{l-2}{k-2}\prod\limits_{i=1}^{n}(du_{i}-1)! \times \prod\limits_{i \in S}\frac{1}{du_{i}-1}\) ，对答案的贡献为 \(\sum\limits_{k=2}^{l}(-1)^{k+1}\dbinom{l-2}{k-2}\prod\limits_{i=1}^{n}(du_{i}-1)! \times \prod\limits_{i \in S}\frac{1}{du_{i}-1}\) ，提出前面 \(\sum\limits_{k=2}^{l}(-1)^{k+1}\dbinom{l-2}{k-2}\) 的系数并改写后得到 \(\sum\limits_{k=0}^{l-2}(-1)^{k+2}\dbinom{l-2}{k}=\sum\limits_{k=0}^{l-2}(-1)^{k}\dbinom{l-2}{k}=[l-2=0]\) 。所以就可以只考虑 \(l=2\) 的情况了，其系数为 \(1\) 。
-
接着考虑容斥，设 \(f_{x}\) 表示以 \(x\) 为根的子树中恰好存在一个链的端点的贡献和，状态转移方程为 \(f_{x}=\begin{cases} -1+\frac{1}{du_{i}-1}\sum\limits_{y \in Son(x)}f_{y}-\frac{1}{du_{i}-1}\sum\limits_{y \in Son(x)}f_{y}=-1 & (fa_{x},x) 是关键边 \\ \frac{1}{du_{i}-1}\sum\limits_{y \in Son(x)}f_{y} & (fa_{x},x) 不是关键边 \end{cases}\) ，其中 \((fa_{x},x)\) 是关键边的三个式子分别对应只选 \((fa_{x},x)\) ，只选子树内部的边，两者都选三种情况。
-
统计答案时类似地合并链上的贡献即可。
点击查看代码
const ll p=1000000007; struct node { ll nxt,to,id; }e[200010]; ll head[200010],du[200010],jc[200010],vis[200010],inv[200010],f[200010],ans=0,cnt=0; void add(ll u,ll v,ll id) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].id=id; head[u]=cnt; } void dfs(ll x,ll fa,ll w) { ll sum=-w; f[x]=-w; ans+=w; for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x,vis[e[i].id]); f[x]=(f[x]+(w==0)*inv[du[x]-1]*f[e[i].to]%p)%p; ans=(ans-inv[du[x]-1]*sum%p*f[e[i].to]%p+p)%p; sum=(sum+f[e[i].to])%p; } } } int main() { // #define Isaac #ifdef Isaac freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); #endif ll c,t,n,k,u,v,i,j; scanf("%lld%lld",&c,&t); jc[0]=jc[1]=inv[0]=inv[1]=1; for(i=2;i<=100000;i++) { jc[i]=jc[i-1]*i%p; inv[i]=(p-p/i)*inv[p%i]%p; } for(j=1;j<=t;j++) { ans=cnt=0; memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); memset(du,0,sizeof(du)); memset(vis,0,sizeof(vis)); scanf("%lld%lld",&n,&k); for(i=1;i<=n-1;i++) { scanf("%lld%lld",&u,&v); add(u,v,i); add(v,u,i); du[u]++; du[v]++; } for(i=1;i<=k;i++) { scanf("%lld",&c); vis[c]=1; } dfs(1,0,0); for(i=1;i<=n;i++) { ans=ans*jc[du[i]-1]%p; } printf("%lld\n",ans); } return 0; }
luogu P7880 [Ynoi2006] rldcot
-
直接在区间虚树上数颜色不太好做。
-
点 \(x\) 会被询问区间 \([l,r]\) 的虚树包含当且仅当 \(x \in [l,r]\) 或存在 \(u,v \in [l,r]\) 且分别属于 \(x\) 的不同子树内。
-
不妨仅考虑包含 \(x\) 的一些极短区间/点对数，即 \(\forall y \in Son(x),u \in Subtree(y),u\) 在 \(Subtree(x)\) 中除 \(Subtree(y)\) 中的前驱 \(pre\) 后继 \(suf\) 构成的点对 \((pre,u),(u,suf)\)，由树上启发式合并可知点对数规模是 \(O(n \log n)\) 。
-
扫描线的过程中记录每种颜色最后一次出现的位置即可。
点击查看代码
struct node { int nxt,to,w; }e[200010]; int head[200010],ans[200010],last[200010],cnt=0; ll d[200010]; vector<pair<int,int> >q[200010],c[200010]; void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } struct BIT { int c[200010]; int lowbit(int x) { return (x&(-x)); } void add(int x,int val) { for(int i=x;i>=1;i-=lowbit(i)) { c[i]+=val; } } int getsum(int n,int x) { int ans=0; for(int i=x;i<=n;i+=lowbit(i)) { ans+=c[i]; } return ans; } }T; struct DSU_On_Tree { ll dis[200010]; int siz[200010],fa[200010],son[200010],dfn[200010],out[200010],pos[200010],tot=0; set<int>s[200010]; void add_rt(int x,int rt) { s[rt].insert(x); } void work_rt(int x,int rt) { set<int>::iterator it=s[rt].upper_bound(x); if(*it!=0x7f7f7f7f) { c[*it].push_back(make_pair(x,dis[rt])); } it=--s[rt].lower_bound(x); if(*it!=0) { c[x].push_back(make_pair(*it,dis[rt])); } } void add_tree(int x,int rt) { for(int i=dfn[x];i<=out[x];i++) { add_rt(pos[i],rt); } } void work_tree(int x,int rt) { for(int i=dfn[x];i<=out[x];i++) { work_rt(pos[i],rt); } } void del_tree(int x) { s[x].clear(); } void dfs1(int x,int father) { tot++; dfn[x]=tot; pos[tot]=x; siz[x]=1; fa[x]=father; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { d[e[i].to]=dis[e[i].to]=dis[x]+e[i].w; dfs1(e[i].to,x); siz[x]+=siz[e[i].to]; son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x]; } } out[x]=tot; } void dfs2(int x,int flag) { for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=son[x]&&e[i].to!=fa[x]) { dfs2(e[i].to,0); } } if(son[x]!=0) { dfs2(son[x],1); } swap(s[x],s[son[x]]); s[x].insert(0); s[x].insert(0x7f7f7f7f); for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=son[x]&&e[i].to!=fa[x]) { work_tree(e[i].to,x); add_tree(e[i].to,x); } } add_rt(x,x); c[x].push_back(make_pair(x,dis[x])); if(flag==0) { del_tree(x); } } }D; int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,m,u,v,w,l,r,i,j; scanf("%d%d",&n,&m); for(i=1;i<=n-1;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } D.dfs1(1,0); sort(d+1,d+1+n); d[0]=unique(d+1,d+1+n)-(d+1); for(i=1;i<=n;i++) { D.dis[i]=lower_bound(d+1,d+1+d[0],D.dis[i])-d; } D.dfs2(1,1); for(i=1;i<=m;i++) { scanf("%d%d",&l,&r); q[r].push_back(make_pair(l,i)); } for(i=1;i<=n;i++) { for(j=0;j<c[i].size();j++) { if(c[i][j].first>last[c[i][j].second]) { T.add(last[c[i][j].second],-1); last[c[i][j].second]=c[i][j].first; T.add(last[c[i][j].second],1); } } for(j=0;j<q[i].size();j++) { ans[q[i][j].second]=T.getsum(n,q[i][j].first); } } for(i=1;i<=m;i++) { printf("%d\n",ans[i]); } return 0; }