시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1716 563 386 31.639%

문제

트리는 N개의 정점과 N-1개의 간선으로 구성된 그래프이다. 트리의 성질 중 하나는 어느 두 정점 간에도 유일하게 하나의 경로가 존재한다는 것이다.

트리의 모든 간선에 음이 아닌 정수인 가중치가 배정되었다. ‘경로의 가중치’란 경로에 해당하는 간선의 곱으로 정의된다. 또한 ‘트리의 가중치’는 트리 상에 가능한 모든 경로에 대해 ‘경로의 가중치’의 합을 의미한다. 문제는 트리가 주어졌을 때 ‘트리의 가중치’를 구하는 것이다.

입력

첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 간선의 가중치는 W라는 것을 의미한다.

출력

첫째 줄부터 트리의 가중치를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
3 2 100
2 1 100

예제 출력 1

10200

예제 입력 2

4
1 2 5
1 3 5
1 4 5

예제 출력 2

90

예제 입력 3

5
1 2 2
2 3 3
4 3 2
5 3 2

예제 출력 3

55
W3sicHJvYmxlbV9pZCI6IjEyODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI5YWNcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWFjZmMgTi0xXHVhYzFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVjMTMxXHVjOWM4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVhYzA0XHVjNWQwXHViM2M0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNWQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWJjMzBcdWM4MTVcdWI0MThcdWM1YzhcdWIyZTQuICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yjc4MCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWI2MTBcdWQ1NWMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViMjk0IFx1ZDJiOFx1YjlhYyBcdWMwYzFcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTc0ICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEEsIEIsIFcoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgVyAmbGU7IDEsMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IEFcdWM4MTBcdWFjZmMgQlx1YzgxMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwIFx1Yzc3NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0IFdcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUFVURVZJIiwiZGVzY3JpcHRpb24iOiI8cD5BcyB5b3UgYXJlIGJvdW5kIHRvIGtub3cgYnkgbm93LCBhIHRyZWUgaXMgYSBjb25uZWN0ZWQgZ3JhcGggY29uc2lzdGluZyBvZiBOIHZlcnRpY2VzIGFuZCBOJm1pbnVzOzEgZWRnZXMuIFRyZWVzIGFsc28gaGF2ZSB0aGUgcHJvcGVydHkgb2YgdGhlcmUgYmVpbmcgZXhhY3RseSBhIHNpbmdsZSB1bmlxdWUgcGF0aCBiZXR3ZWVuIGFueSBwYWlyIG9mIHZlcnRpY2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiBhIHRyZWUgaW4gd2hpY2ggZXZlcnkgZWRnZSBpcyBhc3NpZ25lZCBhIHdlaWdodCAmbmRhc2g7IGEgbm9uLW5lZ2F0aXZlIGludGVnZXIuIFRoZSB3ZWlnaHQgb2YgYSBwYXRoIGlzIHRoZSBwcm9kdWN0IG9mIHRoZSB3ZWlnaHRzIG9mIGFsbCBlZGdlcyBvbiB0aGUgcGF0aC4gVGhlIHdlaWdodCBvZiB0aGUgdHJlZSBpcyB0aGUgc3VtIG9mIHRoZSB3ZWlnaHRzIG9mIGFsbCBwYXRocyBpbiB0aGUgdHJlZS4gUGF0aHMgZ29pbmcgaW4gb3Bwb3NpdGUgZGlyZWN0aW9ucyAoQSB0byBCIGFuZCBCIHRvIEEpIGFyZSBjb25zaWRlcmVkIHRoZSBzYW1lIGFuZCwgd2hlbiBjYWxjdWxhdGluZyB0aGUgd2VpZ2h0IG9mIGEgdHJlZSwgYXJlIGNvdW50ZWQgb25seSBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYSB0cmVlLCBjYWxjdWxhdGVzIGl0cyB3ZWlnaHQgbW9kdWxvIDEgMDAwIDAwMCAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIHRyZWUuIFRoZSB2ZXJ0aWNlcyBhcmUgbnVtYmVyZWQgMSB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiZtaW51czsxIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIgYW5kIFcgKDEgJmxlOyBBLCBCICZsZTsgTiwgMCAmbGU7IFcgJmxlOyAxMDAwKSBkZXNjcmliaW5nIG9uZSBlZGdlLiBUaGUgZWRnZSBjb25uZWN0cyB2ZXJ0aWNlcyBBIGFuZCBCLCBhbmQgaXRzIHdlaWdodCBpcyBXLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgd2VpZ2h0IG9mIHRoZSB0cmVlLCBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2008 > Final Exam #1 2번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: hayman42