Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51580 tengzifan 树上博弈 C++ 解答错误 40 31 MS 6112 KB 1583 2022-07-13 11:53:52

Tests(8/20):


#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,m,semaxx=-1,maxx=-1; vector<pair<int,int> > adj[maxn]; int fa[maxn][20],dep[maxn],c[maxn],cnt=0,a[maxn]; void dfs(int u,int p) { dep[u] = dep[p]+1; fa[u][0]=p; for(int i=1; i<=19; ++i) fa[u][i] = fa[fa[u][i-1]][i-1]; for(int i=0; i<adj[u].size(); ++i) { int v=adj[u][i].first; if(v==p) continue; c[v] = adj[u][i].second; dfs(v,u); } } int lca(int u,int v) { if(dep[u] < dep[v]) swap(u,v); for(int i=19; i>=0; --i) { if(dep[fa[u][i]] >= dep[v]) u=fa[u][i]; } if(u==v) return u; for(int i=19; i>=0; --i) { if(fa[u][i] != fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } void add(int b,int e,int r,int opt) { if(b == e) return ; a[c[b]]+=opt; add(fa[b][0],e,r,opt); } int main() { // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); scanf("%d",&n); for(int i=1; i<n; ++i) { int u,v,val; scanf("%d%d%d",&u,&v,&val); adj[u].push_back(make_pair(v,val)); adj[v].push_back(make_pair(u,val)); } if(n<=2000) { dfs(1,1); scanf("%d",&m); while(m--) { int ans=0; int u,v,r; scanf("%d%d%d",&u,&v,&r); int lc=lca(u,v); add(u,lc,r,1); add(v,lc,r,1); for(int i=r; i>=1; --i) { if(a[i] % 2 == 0) ans++; else break; } printf("%d\n",ans); add(u,lc,r,-1); add(v,lc,r,-1); } } //while(1); return 0; }


测评信息: