标签：cc 小度 long int 挪车 500005 式子
- 子树余树的信息可以通过全局信息减去子树信息来统计
- 在最后一刻，其实你已经意识到，问题大概出在((g[fa][0]-f[n1][0])+n-sum-cnt[n1][0])这个式子上
- 但你最终没能找出错误，因为你只关注到式子的逻辑有没有问题，而没有意识到变量对式子的诠释是否恰当——
- 你需要的其实是O节点的个数，但n代表的是所有节点的总个数
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[500005];
long long s[500005],d[500005],cnt[500005][2],sum,n;
bool c[500005],pd;
long long ans,f[500005][2],g[500005][2];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
cc=getchar();
}
int s=cc-48;
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
return s;
}
void dfs1(int n1,int fa)
{
s[n1]=1;
f[n1][c[n1]]=d[n1];
cnt[n1][c[n1]]=1;
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
d[a[n1][i]]=d[n1]+1;
dfs1(a[n1][i],n1);
s[n1]+=s[a[n1][i]];
f[n1][0]+=f[a[n1][i]][0];
f[n1][1]+=f[a[n1][i]][1];
cnt[n1][0]+=cnt[a[n1][i]][0];
cnt[n1][1]+=cnt[a[n1][i]][1];
}
}
if(s[n1]==sum||n-s[n1]==sum)
{
pd=true;
}
}
void dfs2(int n1,int fa)
{
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
g[n1][0]=g[n1][0]+f[a[n1][i]][0];
g[n1][1]=g[n1][1]+f[a[n1][i]][1];
}
else if(fa!=0)
{
g[n1][0]+=((g[fa][0]-f[n1][0])+n-sum-cnt[n1][0]);
g[n1][1]+=((g[fa][1]-f[n1][1])+sum-cnt[n1][1]);
}
}
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
dfs2(a[n1][i],n1);
}
}
if(s[n1]==sum)
{
ans=min(ans,f[n1][0]+g[fa][1]-f[n1][1]);
}
if(n-s[n1]==sum)
{
ans=min(ans,f[n1][1]+g[fa][0]-f[n1][0]);
}
}
int main()
{
cin>>n;
string s;
cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='P')
{
c[i+1]=true;
sum++;
}
}
for(int i=1;i<n;i++)
{
int u,v;
u=read1();
v=read1();
a[u].push_back(v);
a[v].push_back(u);
}
d[1]=1;
dfs1(1,0);
if(pd==false)
{
puts("-1");
return 0;
}
for(int i=1;i<=n;i++)
{
f[i][0]-=(cnt[i][0]*(d[i]-1));
f[i][1]-=(cnt[i][1]*(d[i]-1));
}
ans=LLONG_MAX;
dfs2(1,0);
cout<<ans<<endl;
return 0;
}
/*
10
OPPPOPPOPO
1 2
2 3
3 4
3 5
1 6
1 7
7 8
7 9
7 10
5
PPPPO
1 2
1 3
1 4
1 5
*/
标签：cc,
小度,
long,
int,
挪车,
500005,
式子
From： https://www.cnblogs.com/watersail/p/18287701