LINK:牛牛的树行棋
本来是不打算写题解的。
不过具体思考 还是有一段时间的。
看完题 一直想转换到阶梯NIM的模型上 转换失败。
考虑SG函数. 容易发现 SG函数\(sg_x=max{sg_{tn}+1}\land tn\in sonx\)
这样就可以判断整个局面的获胜与否 然后就是问所有的第一步可以获胜的方法。
那肯定是给对方一个必败的局面即可 考虑对每个点找答案 那么就是每个点子树内 不包括本身 \(ans\)^\(sg_x\)的出现次数。
dsu on tree确实可以做 不过显得没有必要 线段树合并确实可以做 不过过于麻烦 由于只是单点差值 可以栈内外差分即可。
const int MAXN=500010;
int n,ans,len;ll cnt;
int f[MAXN],c[MAXN];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
inline void add(int x,int y)
{
ver[++len]=y;nex[len]=lin[x];lin[x]=len;
ver[++len]=x;nex[len]=lin[y];lin[y]=len;
}
inline void dfs(int x,int fa)
{
go(x)
{
if(tn!=fa)
{
dfs(tn,x);
f[x]=max(f[x],f[tn]+1);
}
}
}
inline void dp(int x,int fa)
{
int need=ans^f[x];
int ww=need<=n?c[need]:0;
go(x)
{
if(tn!=fa)
{
dp(tn,x);
}
}
cnt+=(need<=n?c[need]:0)-ww;
++c[f[x]];
}
int main()
{
//freopen("1.in","r",stdin);
get(n);
rep(2,n,i)add(read(),read());
dfs(1,0);
rep(1,n,i)ans=ans^f[i];
if(!ans){puts("NO");return 0;}
else
{
puts("YES");
dp(1,0);
putl(cnt);
}
return 0;
}