题意:给一棵有权无根树,定义树上两点的路径 d(u,v) = uv 路径上的边权的异或和。分别求出使得 d(u,v) = x , x\in[0,2^{16}) 的路径有多少条。
解法:随便选一个点做根,那么 d(u,v) = d(root,u) \oplus d(root,v) ,那么答案就可以通过将所有 d(u,root) 做一遍 FWT 得到。

#include <bits/stdc++.h>
#include <ext/rope>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define X first
#define Y second
#define scd(a) scanf("%d", &a)
#define scdd(a,b) scanf("%d%d", &a, &b)
#define scddd(a,b,c) scanf("%d%d%d", &a, &b,&c)
#define mset(var,val) memset(var, val, sizeof(var))
#define MP make_pair
#define PB push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-9;

template <class T>
void test(T t){
    cout<<t<<"\n";
}
template <class T, class T2>
void test(T t, T2 t2){
    cout<<t<<" "<<t2<<"\n";
}
template <class T, class T2, class T3>
void test(T t, T2 t2, T3 t3){
    cout<<t<<" "<<t2<<" "<<t3<<"\n";
}

const int N = 1e5+10;
struct Edge{
    int to, next, w;
}edge[N<<1];
int head[N];
int tot;
void add_edge(int u, int v, int w){
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int dp[N];

void dfs(int u, int fa){
    for(int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if(v != fa){
            dp[v] = dp[u] ^ edge[i].w;
            dfs(v, u);
        }
    }
}

void FWT(ll *a, int n){
    for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;++j){
        ll x = a[i+j],y=a[i+j+d];
        a[i+j]=x+y,a[i+j+d]=x-y;
    }
}

void UFWT(ll *a, int n){
    for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;++j){
        ll x = a[i+j],y=a[i+j+d];
        a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
    }
}

ll a[N];
ll b[N];

int T = 1;
void testcase(){
    printf("Case %d:\n", T++);
}

void work(){
    int n;
    scd(n);
    rep1(i,n){
        head[i] = -1;
    }
    tot = 0;
    rep(i,n-1){
        int u, v, w;
        scddd(u, v, w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dp[1] = 0;
    dfs(1, 0);
    rep(i,1<<16){
        a[i] = b[i] = 0;
    }
    rep1(i,n){
        a[dp[i]]++;
        b[dp[i]]++;
    }
    FWT(a,1<<16);
    FWT(b,1<<16);
    rep(i,1<<16){
        a[i] *= b[i];
    }
    UFWT(a,1<<16);
    a[0] -= n;
    testcase();
    rep(i,1<<16){
        printf("%lld\n", a[i]/2);
    }
}


int main(int argc, const char * argv[]) {
    #ifdef local
        freopen("in.txt", "r", stdin);
    #endif // local
    int t;
    scd(t);
    for(;t--;)
        work();
    return 0;
}

分类: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注

隐藏
变装