约束条件
题意
给定一些关系\(x=y 或x\neq y\)。求是否能满足。
分析
显然并查集。我们考虑将约束条件排序，先使形如\(x_{i}=x_{j}\)的\(x_{i}\)和\(x_{j}\)合并。而后我们观察是否存在\(x_{i}\)和\(x_{j}\)已经合并但是关系是\(\neq\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int T;
int b[N];
int fa[N];
int n,cnt;
struct node{
int e,x,y;
}a[N];
bool cmp(node a,node b){
return a.e>b.e;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
cin>>T;
while(T--){
cnt=0;
memset(a,0,sizeof a);
memset(b,0,sizeof b);
for(int i=1;i<=N;i++) fa[i]=i;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
b[++cnt]=a[i].x,b[++cnt]=a[i].y;
}
sort(b+1,b+1+cnt);
int m=unique(b+1,b+1+cnt)-b-1;
for(int i=1;i<=n;i++){
a[i].x=lower_bound(b+1,b+1+m,a[i].x)-b;
a[i].y=lower_bound(b+1,b+1+m,a[i].y)-b;
}
sort(a+1,a+1+n,cmp);
bool flag=1;
for(int i=1;i<=n;i++){
int fx=find(a[i].x),fy=find(a[i].y);
if(fx==fy&&!a[i].e) {printf("NO\n");flag=0;break;}
if(fx!=fy&&a[i].e) fa[fx]=fy;
}
if(flag) printf("YES\n");
}
return 0;
}
CF379F
题意
一个树，只含有三个并列节点和一个根。一共\(q\)次操作，每次操作可以在叶节点上加入两个子节点，而后请输出每次操作后树的直径。
分析
设原来树的直径路径为\(l\to{r}\)，那么本次在\(x\)后加两个子节点\(n+1,n+2\)，我们显然有树的直径可以为\(l\to{r}\)或\(l\to{n+1}\)或\(r\to{n+1}\)。而后我们只需要倍增维护\(n+1,n+2\)的倍增\(Fa\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int dep[N],fat[N];
int cnt,head[N],nxt[N],to[N],val[N];
int f[N][25];
int dis[N];
// void add(int u,int v,int w){
// cnt++;to[cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;
// }
// void dfs(int x,int fa){
// for(int i=head[x];i;i=nxt[i]){
// int y=to[i];
// if(y==fa) continue;
// dep[y]=dep[x]+1;dis[y]=dis[x]+val[i];fat[y]=x;dfs(y,x);
// }
// }
int n,m;
// void init(){
// for(int i=1;i<=n;i++) f[i][0]=fat[i];
// for(int j=1;j<=20;j++){
// for(int i=1;i<=n;i++){
// f[i][j]=f[f[i][j-1]][j-1];
// }
// }
// }
int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
if (dep[x] != dep[y]) {
for (int i = 20; i >= 0; i--)
if (dep[f[x][i]] > dep[y])
x = f[x][i];
x = f[x][0];
}
if (x == y)
return x;
for (int i = 20; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int len=2;
int q;
int x;
int main(){
// freopen("in.txt","r",stdin);
n=4;
f[2][0]=f[3][0]=f[4][0]=1;
int a=2,b=3;
dep[1]=0,dep[2]=dep[3]=dep[4]=1;
cin>>q;
for(int i=1;i<=q;i++){
int u=n+1,v=n+2;
n+=2;
scanf("%d",&x);
f[u][0]=f[v][0]=x;
dep[u]=dep[v]=dep[x]+1;
for(int j=1;(1<<j)<=n;j++){
f[u][j]=f[f[u][j-1]][j-1];
f[v][j]=f[f[v][j-1]][j-1];
}
int _lca=lca(a,u);
if(dep[u]+dep[a]-dep[_lca]*2>len) b=u,len++;
_lca=lca(b,u);
if(dep[u]+dep[b]-dep[_lca]*2>len) a=u,len++;
printf("%d\n",len);
}
return 0;
}
CF1296F
题意
给你一颗大小为 \(n\) 的无根树，树边的边权尚未确定。现在你从 \(m\) 个人中得知在 \((u,v)\) 这条路径(最短路径)上的最小边权为 \(w\) 。请你构造一种方案满足这 \(m\) 个人的条件，如果不存在，请输出 \(-1\)。
分析
我们显然可以先把边权按照从小到大排序，而后构造一种最优方案即把这条路径上的所有边都赋值为 \(w\)。这样我们可以使得每条路径上的最小值都尽可能满足题面的要求。而后我们检验是否合法。使用 \(LCA\) 维护即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
struct node{int u,v,w;}a[N];
int f[N][50];
int head[N],to[N],nxt[N];
int fat[N];
int dis[N],dep[N];
int cnt;
int n,m;
int num[N];
int w[N];
void add(int u,int v){
cnt++;to[cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
int xx;
void dfs(int x,int fa){
++xx;
if (xx > 1e6) exit(0);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
num[y]=(i+1)/2;
dep[y]=dep[x]+1;fat[y]=x;dfs(y,x);
}
}
void init(){
for(int i=1;i<=n;i++) f[i][0]=fat[i];
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
if (dep[x] != dep[y]) {
for (int i = 20; i >= 0; i--)
if (dep[f[x][i]] > dep[y])
x = f[x][i];
x = f[x][0];
}
if (x == y)
return x;
for (int i = 20; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
void modify(int u,int v,int val){
int _lca=lca(u,v);
while(u!=_lca) w[num[u]]=val,u=f[u][0];
while(v!=_lca) w[num[v]]=val,v=f[v][0];
}
int query(int u,int v){
int _lca=lca(u,v);
int res=0x3f3f3f3f;
while(u!=_lca) res=min(res,w[num[u]]),u=f[u][0];
while(v!=_lca) res=min(res,w[num[v]]),v=f[v][0];
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
init();
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+1,a+1+m,[](const node a,const node b){return a.w<b.w;});
// for(int i=1;i<=m;i++) printf("%d\n",a[i].w);
// for(int i=1;i<=n;i++) printf("%d\n",num[i]);
for(int i=1;i<=m;i++) modify(a[i].u,a[i].v,a[i].w);
bool flag=0;
for(int i=1;i<=m;i++){
// printf("%d ",query(a[i].u,a[i].v));
if(query(a[i].u,a[i].v)!=a[i].w){flag=1;break;}
}
if(flag) printf("-1\n");
else{
for(int i=1;i<=n-1;i++){
printf("%d ",w[i]?w[i]:1);
}
// printf("%d\n",w[n-1]?w[n-1]:1);
}
return 0;
}