結果

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

ソースコード

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();
        long ans = 0;
        long P = 1000000007;
        ArrayList<ArrayList<ArrayList<Integer>>> edge = new ArrayList<>();
        for( int i = 0; i < 30; i++ ) {
            edge.add(new ArrayList<>());
            for( int j = 0; j < N; j++ ) {
                edge.get(i).add(new ArrayList<>());
            }
        }
        
        for( int i = 0; i < N-1; i++ ) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            int c = sc.nextInt();
            for( int j = 0; j < 30; j++ ) {
                if( (c>>j)%2 == 1 ) {
                    edge.get(j).get(a).add(b);
                    edge.get(j).get(b).add(a);
                }
            }
        }
        
        // for( int i = 1; i < N; i++ ) {
        //     pw.println(edge.get(0).get(i));
        // }
        
        for( int i = 0; i < 30; i++ ) {
            long k = modpow(2,i,P);
            LinkedList<Integer> queue = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            for( int j = 0; j < N; j++ ) {
                if( visited.contains(j) ) continue;
                queue.offer(j);
                long cnt = 0;
                while( !queue.isEmpty() ) {
                    int now = queue.poll();
                    if( !visited.add(now) ) continue;
                    cnt++;
                    for( int next : edge.get(i).get(now) ) {
                        if( !visited.contains(next) ) queue.offer(next);
                    }
                }
                ans += cnt*(cnt-1)/2%P*k%P;
                ans %= P;
                // pw.println(ans+" "+i+" "+j);
            }
        }
        
        pw.println(ans);
        
    }
    
    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