题意:T组数据,每次给你1e5个点的树(1为根),每个点有一权值,询问1-n每个节点的子树中,
至少修改几个点的权值(每次都可以任意修改),才能让子树中任意2点的距离==他们权值差的绝对值
无解输出-1
题解:画图不难发现,如果这个节点有3个儿子,也就是不包含它连向它父亲的边,它还有多于2条边的话,一定不行
因为子节点权值只能是这个节点+1或者-1,所以只能存在最多2个
那我们就又发现了,只有这个子树,可以拉成一个链的时候,才有答案,
考虑在链中的情况,如何判断修改最少的个数,使得这是个差为1的等差数列
一个显然的做法,每个数减去i,比如1 4 3 5 6 3 7,每个数减去位置0 2 0 1 2 -3 0
众数是0,有3个,所以答案就是7-3==4,至少修改4个数
我们再考虑合并的情况,可以使用启发式合并,每次让儿子数少的并向多的
可是我们又发现,这个节点一旦是2棵子树合并过了,他这颗子树就废掉了,以后就不会再用了
因为这个链已经使用了,而继续传回去的点是这个父节点,它又不在链的两端,所以总的复杂度O(n)
多组数据的清空怕T,所以在使用后,马上进行了清空,代码有点冗余
#include<bits/stdc++.h>
using namespace std;
#define N 100007
int n,v[N],siz[N],de[N],vis[N],T,u,w;
vector<int> g[N];
int now,cnt1[][N*],mx1[],cnt2[][N*],mx2[];
int nod[][N],tot[],ad[N*],mxx,ans[N];
bool dfs(int x,int dep)
{
vis[x]=;
siz[x]=;
de[x]=dep;
bool re=;
int cnt=;
for(int i=;i<g[x].size();i++)
if(!vis[g[x][i]])
{
if(cnt != )
{
now^=;
mx1[now]=mx2[now]=;
for(int j=;j<=tot[now];j++)
{
int xx=nod[now][j];
cnt1[now][v[xx]-de[xx]]=;
cnt2[now][v[xx]+de[xx]]=;
}
tot[now]=;
}
re&=dfs(g[x][i],dep+),siz[x]+=siz[g[x][i]];
cnt++;
}
if(!re || g[x].size()> || (x== && g[x].size()==))
{
ans[x]=-;
return ;
}
if(g[x].size()== || (x== && g[x].size()==))
{
int tmp = ;
mxx = ;
for(int i = ; i <= tot[now]; i++)
{
int xx = nod[now][i];
ad[v[xx] - tmp]++; mxx = max(mxx, ad[v[xx] - tmp]); tmp++;
}
ad[v[x] - tmp]++; mxx = max(mxx, ad[v[x] - tmp]); tmp++;
for(int i = tot[now ^ ]; i >= ; i--)
{
int xx = nod[now ^ ][i];
ad[v[xx] - tmp]++; mxx = max(mxx, ad[v[xx] - tmp]); tmp++;
}
ans[x] = siz[x] - mxx; tmp = ;
for(int i = ; i <= tot[now]; i++)
{
int xx = nod[now][i];
ad[v[xx] - tmp]--; tmp++;
}
ad[v[x] - tmp]--; tmp++;
for(int i = tot[now ^ ]; i >= ; i--)
{
int xx = nod[now ^ ][i];
ad[v[xx] - tmp]--; tmp++;
} tmp = ;
mxx = ;
for(int i = ; i <= tot[now]; i++)
{
int xx = nod[now][i];
ad[v[xx] + tmp]++; mxx = max(mxx, ad[v[xx] + tmp]); tmp++;
}
ad[v[x] + tmp]++; mxx = max(mxx, ad[v[x] + tmp]); tmp++;
for(int i = tot[now ^ ]; i >= ; i--)
{
int xx = nod[now ^ ][i];
ad[v[xx] + tmp]++; mxx = max(mxx, ad[v[xx] + tmp]); tmp++;
}
ans[x] = min(ans[x], siz[x] - mxx);
tmp = ;
for(int i = ; i <= tot[now]; i++)
{
int xx = nod[now][i];
ad[v[xx] + tmp]--; tmp++;
}
ad[v[x] + tmp]--; tmp++;
for(int i = tot[now ^ ]; i >= ; i--)
{
int xx=nod[now^][i];
ad[v[xx]+tmp]--;tmp++;
}
return ;
}
nod[now][++tot[now]]=x;
cnt1[now][v[x]-dep]++;
if(cnt1[now][v[x]-dep]>mx1[now]) mx1[now]=cnt1[now][v[x]-dep];
cnt2[now][v[x]+dep]++;
if(cnt2[now][v[x]+dep]>mx2[now]) mx2[now]=cnt2[now][v[x]+dep];
ans[x]=siz[x]-max(mx1[now], mx2[now]);
return ;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
now=;
mx1[now]=mx2[now]=;
for(int j=;j<=tot[now];j++)
{
int xx=nod[now][j];
cnt1[now][v[xx]-de[xx]]=;
cnt2[now][v[xx]+de[xx]]=;
}
tot[now]=;
now=;
mx1[now]=mx2[now]=;
for(int j=;j<=tot[now];j++)
{
int xx=nod[now][j];
cnt1[now][v[xx]-de[xx]]=;
cnt2[now][v[xx]+de[xx]]=;
}
tot[now] = ;
now = ;
for(int i=;i<=n;i++) vis[i]=,ans[i]=;
for(int i=;i<=n;i++) g[i].clear();
for(int i=;i<=n;i++) scanf("%d",&v[i]),v[i]+=;
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&w);
g[u].push_back(w);
g[w].push_back(u);
}
dfs(,);
for(int i = ; i <= n; i++) printf("%d ", ans[i]);
puts("");
}
}
不挤在一次dfs里好像就短多了
#include<bits/stdc++.h>
#define lld long long
#define N 300007
using namespace std;
int T,n,nn,pn,u,w;
int v[N],dep[N],fa[N],dp[N],dq[N];
int ch[N],ok[N],p[N],ans[N],sz[N];
vector<int> g[N];
void DFS(int x)
{
for (auto e: g[x]) if (e!=fa[x]) DFS(e);
p[pn++]=x;
}
void work(int id)
{
int t;
for (int i=;i<pn;i++)
{
if (id==-) t=p[i];else t=id;
ans[t]=max(ans[t],++dq[v[p[i]]+i]);
ans[t]=max(ans[t],++dp[v[p[i]]-i]);
if (i && id==-) ans[p[i]]=max(ans[p[i]],ans[p[i-]]);
}
for (int i=;i<pn;i++)
{
dp[v[p[i]]-i]--;
dq[v[p[i]]+i]--;
}
}
void solve(int x)
{
pn=;
DFS(x);
work(-);
}
void solve2(int x)
{
pn=;
int tn=-;
for (auto e: g[x]) if (e!=fa[x])
{
DFS(e);
if (tn==-)
{
p[pn++]=x;
tn=pn;
}
}
reverse(p+tn,p+pn);
work(x);
}
void dfs(int x)
{
ok[x]=sz[x]=;
ch[x]=;
for (auto e:g[x]) if (e!=fa[x])
{
ch[x]++;
fa[e]=x;
dfs(e);
sz[x]+=sz[e];
ok[x]&=ok[e];
}
ok[x]&=ch[x]<=;
if (!ok[x])
{
for (auto e:g[x]) if (e!=fa[x] && ok[e]) solve(e);
if (ch[x]==)
{
int c=;
for (auto e:g[x]) if (e!=fa[x] && ok[e]) c++;
if (c==) solve2(x);
}
}
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=;i<n;i++)
{
g[i].clear();
scanf("%d",&v[i]);
v[i]+=n;
ans[i]=-;
}
for (int i=;i<n;i++)
{
scanf("%d%d",&u,&w);
u--;w--;
g[u].emplace_back(w);
g[w].emplace_back(u);
}
fa[]=-;
dfs();
if (ok[]) solve();
for (int i=;i<n;i++) printf("%d ",ans[i]==-?-:sz[i]-ans[i]);
puts("");
}
}