牛客2022提高组赛前集训第四场 T1博弈

题意：

即一棵树，有u、v两点，S为从u到v路径上所有边权值的集合。

有A、B两人，从S中取数，必须小于等于前一个数，取不了的人输

问有多少初始点对(u,v)，可以使A（先手）有必胜策略

输入：

本题采用捆绑测试，第一行一个正整数 ?，表示数据组数。

对于每一组数据，描述一棵树。

第一行一个正整数 ?，表示树的大小。

接下来 ? − 1 行，每行三个数 ?, ?, ?，代表树上有一条边权为 ? 的，连接点 ?，点 ? 的边。

输出：

对于每组输入，输出可以使A有必胜策略的初始点对（u,v)数量

MY CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>inline void read(T &x){
    x=0; 
    T w=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=w;
}
const int maxn=5e5+5;
ll T,n,num,h[maxn],to[maxn<<1],edge[maxn<<1],nxt[maxn<<1];
void adde(ll u,ll v,ll w){
    to[++num]=v,edge[num]=w,nxt[num]=h[u],h[u]=num;
}
ll ans;
ll W[maxn],m;
ull dis[maxn];
ull po[maxn];
unordered_map<ull,ll>mp;
void init(){
    po[0]=1;
    for(int i=1;i<=maxn-5;++i)po[i]=po[i-1]*131;
}
void dfs(ll now,ll fa){
    for(int i=h[now];i;i=nxt[i]){
        ll nx=to[i];
        if(nx==fa)continue;
        dis[nx]=dis[now]^po[lower_bound(W+1,W+m+1,edge[i])-W];
        dfs(nx,now);
    }
}
void solve(){
    read(n);
    num=0;
    for(int i=1;i<=n;++i)h[i]=0;
    for(int i=1,u,v,w;i<n;++i){
        read(u),read(v),read(w);
        adde(u,v,w);
        adde(v,u,w);
        W[i]=w;
    }
    sort(W+1,W+n);
    m=unique(W+1,W+n)-W-1;
    dfs(1,0);
    ans=ans+n*(n-1)/2;
    mp.clear();
    for(int i=1;i<=n;++i)ans-=mp[dis[i]],++mp[dis[i]];
    printf("%lld\n",ans);
    return ;
}
int main(){
    
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    init();
    read(T);
    while(T--)solve();
    
    return 0;
}

是不是很像牛客上的TJ？

是的，就是对着TJ改的，Debug的时候实在破防了，只能对着改（真的没有CTJ）

得分：34pts

$\color{red}{WA}$ on 1,2,4,5,6,7,11,12

求条！