很好没有模拟赛。
很不好为什么是树上问题。
[A]
题意其实就是给你一棵树，问树上某条路径是否存在颜色 c 的点。
很显然我是纸张，因此直接树链剖分，将原本树上的某条路径转成不超过 \log(n) 个区间；
对于每个区间的颜色，我们直接使用 vector 维护，lower_bound 查询。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5,INF=1e9;
typedef long long LL;
int n,m,w[N];
int h[N],e[M],ne[M],idx;
int id[N],new_w[N],cnt;
int d[N],Size[N],top[N],par[N],son[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs1(int u,int father,int dep)
{
d[u]=dep;
par[u]=father;
Size[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father)continue;
dfs1(j,u,dep+1);
Size[u]+=Size[j];
if(Size[son[u]]<Size[j])son[u]=j;
}
}
vector<int>color[N];
void dfs2(int u,int t)
{
id[u]=++cnt;
top[u]=t;
new_w[cnt]=w[u];
if(!son[u])return;
dfs2(son[u],t);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==par[u]||j==son[u])continue;
dfs2(j,j);
}
}
int query(int l,int r,int c)
{
auto pos=lower_bound(color[c].begin(),color[c].end(),l);
if(pos!=color[c].end()&&*pos<=r)return 1;
else return 0;
}
int query_path(int u,int v,int c)
{
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]])swap(u,v);
if(query(id[top[u]],id[u],c))return 1;
u=par[top[u]];
}
if(d[u]<d[v])swap(u,v);
if(query(id[v],id[u],c))return 1;
return 0;
}
vector<int>res;
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs1(1,-1,1);
dfs2(1,1);
for(int i=1;i<=cnt;i++)color[new_w[i]].push_back(i);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(query_path(a,b,c))res.push_back(1);
else res.push_back(0);
}
for(auto i:res)printf("%d",i);
return 0;
}
[B]
题意很短就不翻译了
注意到每一棵子树的父节点编号都小于自身，因此我们可以 dfs 树1,，将树1的子树在树2上将所对应区间标出。
当我们加入一个区间的时候，如果它被其他区间包含，我们就把包含它的区间换掉。如果
它包含了原来的区间，那么加入它肯定不优。最后返回时撤销刚才得操作就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef long long LL;
int n;
int h1[N],h2[N],e[N<<1],ne[N<<1],idx;
int dfn[N],low[N],timestamp;
int tr[N<<2],tag[N<<2];
void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void pushdown(int u)
{
if(~tag[u])
{
tr[u<<1]=tag[u<<1]=tr[u<<1|1]=tag[u<<1|1]=tag[u];
tag[u]=-1;
}
}
void modify(int u,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R)
{
tr[u]=tag[u]=v;
return;
}
pushdown(u);
int mid=l+r>>1;
if(L<=mid)modify(u<<1,l,mid,L,R,v);
if(mid<R)modify(u<<1|1,mid+1,r,L,R,v);
tr[u]=max(tr[u<<1],tr[u<<1|1]);
}
int query(int u,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tr[u];
pushdown(u);
int mid=l+r>>1,res=-1e9;
if(L<=mid)res=max(res,query(u<<1,l,mid,L,R));
if(mid<R)res=max(res,query(u<<1|1,mid+1,r,L,R));
return res;
}
void dfs1(int u)
{
dfn[u]=++timestamp;
for(int i=h2[u];~i;i=ne[i])
{
int j=e[i];
dfs1(j);
}
low[u]=timestamp;
}
int res,ans;
void dfs2(int u)
{
int t=query(1,1,n,dfn[u],low[u]);
if(t)modify(1,1,n,dfn[t],low[t],0);
else ans++;
modify(1,1,n,dfn[u],low[u],u);
res=max(res,ans);
for(int i=h1[u];~i;i=ne[i])
{
int j=e[i];
dfs2(j);
}
if(t)modify(1,1,n,dfn[t],low[t],t);
else
{
modify(1,1,n,dfn[u],low[u],0);
ans--;
}
}
void work()
{
scanf("%d",&n);
for(int i=1;i<=(n<<1);i++)
{
if(i<=n)h1[i]=h2[i]=-1;
tr[i]=0;
tag[i]=-1;
}
res=ans=idx=timestamp=0;
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
add(h1,x,i);
}
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
add(h2,x,i);
}
dfs1(1);
dfs2(1);
printf("%d\n",res);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)work();
return 0;
}
[C]
由于边权互不相同，因此MST唯一，先用kruskal/prim 求出。
接下来考虑此算法出bug的情况。
我们发现，只要存在横叉边，那么这个算法就会出现问题。
我们先随便选定一个点为根，然后考虑每一条不在MST的边 (a,b)，如果互相没有祖先后代关
系，那么所有在 root-a-b 中的点都不符合要求。
如果 a 是 b 的祖先，那么设 x 为 a 的子节点中是 b 的祖先的那个儿子。所有在 x-b 的点都不符合要求。
using namespace std;
const int N=1e5+5,M=2e5+5;
typedef pair<int,int> PII;
int n,m,st[M],par[N];
#define x first
#define y second
int find(int x)
{
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
PII edge[M];
vector<int>G[N];
int d[N],fa[N][25],s[N];
void dfs1(int u,int father)
{
d[u]=d[father]+1;
fa[u][0]=father;
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto j:G[u])
{
if(j==father)continue;
dfs1(j,u);
}
}
int LCA(int a,int b)
{
if(d[a]<d[b])swap(a,b);
for(int k=20;~k;k--)
{
if(d[fa[a][k]]>=d[b])a=fa[a][k];
}
if(a==b)return a;
for(int k=20;~k;k--)
{
if(fa[a][k]!=fa[b][k])
{
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}
void dfs2(int u,int father)
{
s[u]+=s[father];
for(int j:G[u])
{
if(j==father)continue;
dfs2(j,u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)par[i]=i;
for(int i=1,cnt=0;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
edge[i]={a,b};
a=find(a),b=find(b);
if(a==b)continue;
if(cnt<n-1)
{
st[i]=1;
G[edge[i].x].push_back(edge[i].y);
G[edge[i].y].push_back(edge[i].x);
par[a]=b;
cnt++;
}
}
dfs1(1,0);
for(int i=1;i<=m;i++)
{
if(!st[i])
{
int a=edge[i].x,b=edge[i].y;
int lca=LCA(a,b);
if(d[a]>d[b])swap(a,b);
if(lca==a)
{
s[1]++;
s[b]++;
for(int k=20;~k;k--)
{
if(d[fa[b][k]]>d[a])b=fa[b][k];
}
s[b]--;
}
else
{
s[a]++;
s[b]++;
}
}
}
dfs2(1,0);
for(int i=1;i<=n;i++)printf((s[i]==m-n+1)?"1":"0");
return 0;
}