結果

問題 No.1843 Tree ANDistance
ユーザー ripity
提出日時 2022-02-18 22:29:38
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,355 bytes
コンパイル時間 2,351 ms
コンパイル使用メモリ 79,928 KB
実行使用メモリ 97,808 KB
最終ジャッジ日時 2024-06-29 09:19:07
合計ジャッジ時間 9,337 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 3 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.io.*;

public class Main {
    
    public static Scanner sc = new Scanner(System.in);
    public static PrintWriter pw = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        
        int t = 1;
        while( t > 0 ) {
            solve();
            t--;
        }
        
        pw.flush();
        
    }
    
    static void solve() {
        
        int N = sc.nextInt();
        int[] a = new int[N-1];
        int[] b = new int[N-1];
        int[] c = new int[N-1];
        long ans = 0;
        long P = 1000000007;
        
        for( int i = 0; i < N-1; i++ ) {
            a[i] = sc.nextInt()-1;
            b[i] = sc.nextInt()-1;
            c[i] = sc.nextInt();
        }
        
        for( int i = 0; i < 30; i++ ) {
            long k = modpow(2,i,P);
            ans += bfs(N,a,b,c,i,k,P);
            ans %= P;
        }
        
        pw.println(ans);
        
    }
    
    static long bfs(int N, int[] a, int[] b, int[] c, int d, long k, long P) {
        
        long res = 0;
        ArrayList<ArrayList<Integer>> edge = new ArrayList<>();
        for( int i = 0; i < N; i++ ) {
            edge.add(new ArrayList<>());
        }
        
        for( int i = 0; i < N-1; i++ ) {
            if( (c[i]>>d)%2 == 1 ) {
                edge.get(a[i]).add(b[i]);
                edge.get(b[i]).add(a[i]);
            }
        }
        
        LinkedList<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N];
        for( int j = 0; j < N; j++ ) {
            if( visited[j] ) continue;
            queue.offer(j);
            long cnt = 0;
            while( !queue.isEmpty() ) {
                int now = queue.poll();
                if( visited[now] ) continue;
                visited[now] = true;
                cnt++;
                for( int next : edge.get(now) ) {
                    if( !visited[next] ) queue.offer(next);
                }
            }
            res += cnt*(cnt-1)/2%P*k%P;
            res %= P;
        }
        
        return res;
        
    }
    
    static long modpow( long x, long n, long mod ) {
		
		if( n == 0 ) {
			return 1;
		}
		
		long k = 1;
		while( n > 1 ) {
			if( n%2 == 1 ) k *= x;
			x *= x;
			n /= 2;
			x %= mod;
			k %= mod;
		}
		
		return (k*x)%mod;
		
	}
    
}
0