시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2100 692 476 31.861%

문제

트리는 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
W3sicHJvYmxlbV9pZCI6IjEyODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI5YWNcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWFjZmMgTi0xXHVhYzFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVjMTMxXHVjOWM4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVhYzA0XHVjNWQwXHViM2M0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNWQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWJjMzBcdWM4MTVcdWI0MThcdWM1YzhcdWIyZTQuICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yjc4MCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWI2MTBcdWQ1NWMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViMjk0IFx1ZDJiOFx1YjlhYyBcdWMwYzFcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTc0ICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEEsIEIsIFcoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgVyAmbGU7IDEsMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IEFcdWM4MTBcdWFjZmMgQlx1YzgxMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwIFx1Yzc3NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0IFdcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQVVRFVkkiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHlvdSBhcmUgYm91bmQgdG8ga25vdyBieSBub3csIGEgdHJlZSBpcyBhIGNvbm5lY3RlZCBncmFwaCBjb25zaXN0aW5nIG9mIE4gdmVydGljZXMgYW5kIE4mbWludXM7MSBlZGdlcy4gVHJlZXMgYWxzbyBoYXZlIHRoZSBwcm9wZXJ0eSBvZiB0aGVyZSBiZWluZyBleGFjdGx5IGEgc2luZ2xlIHVuaXF1ZSBwYXRoIGJldHdlZW4gYW55IHBhaXIgb2YgdmVydGljZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgdHJlZSBpbiB3aGljaCBldmVyeSBlZGdlIGlzIGFzc2lnbmVkIGEgd2VpZ2h0ICZuZGFzaDsgYSBub24tbmVnYXRpdmUgaW50ZWdlci4gVGhlIHdlaWdodCBvZiBhIHBhdGggaXMgdGhlIHByb2R1Y3Qgb2YgdGhlIHdlaWdodHMgb2YgYWxsIGVkZ2VzIG9uIHRoZSBwYXRoLiBUaGUgd2VpZ2h0IG9mIHRoZSB0cmVlIGlzIHRoZSBzdW0gb2YgdGhlIHdlaWdodHMgb2YgYWxsIHBhdGhzIGluIHRoZSB0cmVlLiBQYXRocyBnb2luZyBpbiBvcHBvc2l0ZSBkaXJlY3Rpb25zIChBIHRvIEIgYW5kIEIgdG8gQSkgYXJlIGNvbnNpZGVyZWQgdGhlIHNhbWUgYW5kLCB3aGVuIGNhbGN1bGF0aW5nIHRoZSB3ZWlnaHQgb2YgYSB0cmVlLCBhcmUgY291bnRlZCBvbmx5IG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiBhIHRyZWUsIGNhbGN1bGF0ZXMgaXRzIHdlaWdodCBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgdHJlZS4gVGhlIHZlcnRpY2VzIGFyZSBudW1iZXJlZCAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOJm1pbnVzOzEgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiBhbmQgVyAoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgVyAmbGU7IDEwMDApIGRlc2NyaWJpbmcgb25lIGVkZ2UuIFRoZSBlZGdlIGNvbm5lY3RzIHZlcnRpY2VzIEEgYW5kIEIsIGFuZCBpdHMgd2VpZ2h0IGlzIFcuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSB3ZWlnaHQgb2YgdGhlIHRyZWUsIG1vZHVsbyAxIDAwMCAwMDAgMDA3LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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