problem
一棵树,有root,一个点只能向根跳k步直到不能走,问先手必败还是必胜。
root从1到n,回答n次
solution
一次的话就是一个阶梯nim。
多次的话,就要换根。
换根的话,虽然会全局影响,但是对答案没啥影响。
tips
这里的dp是dp[n][2k]不是dp[n][k]][0/1]
code
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
using namespace std;
const int _=1e6+7;
// const int mod=1e9+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
vector<int> g[_];
int dep[_],a[_],n,k,f[_][44],ans[_];
void dfs_init(int u,int fa) {
dep[u]=dep[fa]+1;
f[u][0]=a[u];
for(auto v:g[u]) {
if(v==fa) continue;
dfs_init(v,u);
for(int i=0;i<2*k;++i) {
f[u][i]^=f[v][(i-1+2*k)%(2*k)];
}
}
}
void dfs(int u,int fa) {
// cout<<u<<" "<<fa<<"!\n";
for(int i=k;i<2*k;++i) ans[u]^=f[u][i];
for(auto v:g[u]) {
if(v==fa) continue;
array<int,40> uu,vv;
for(int i=0;i<2*k;++i) {
uu[i]=f[u][i];
vv[i]=f[v][i];
}
for(int i=0;i<2*k;++i) {
f[u][i]^=f[v][(i-1+2*k)%(2*k)];
}
for(int i=0;i<2*k;++i) {
f[v][i]^=f[u][(i-1+2*k)%(2*k)];
}
dfs(v,u);
for(int i=0;i<2*k;++i) {
f[u][i]=uu[i];
f[v][i]=vv[i];
}
}
}
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
#endif
n=read(),k=read();
for(int i=1;i<n;++i) {
int x=read(),y=read();
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;++i) a[i]=read();
int rt=1;
dep[0]=-1;
dfs_init(rt,0);
dfs(rt,0);
for(int i=1;i<=n;++i) cout<<(bool)ans[i]<<" ";
return 0;
}
标签:dep,int,fa,Game,CF1498F,Christmas,dp
From: https://www.cnblogs.com/acmnb/p/16590920.html