{"problem":{"name":"Virus Tree 2","description":{"content":"You are given a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertex $a_i$ and $b_i$. You have coloring materials of $K$ colors. For each ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc133_e"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertex $a_i$ and $b_i$.\nYou have coloring materials of $K$ colors. For each vertex in the tree, you will choose one of the $K$ colors to paint it, so that the following condition is satisfied:\n\n*   If the distance between two different vertices $x$ and $y$ is less than or equal to two, $x$ and $y$ have different colors.\n\nHow many ways are there to paint the tree? Find the count modulo $1\\ 000\\ 000\\ 007$.\n\nWhat is tree? A tree is a kind of graph. For detail, please see: [Wikipedia \"Tree (graph theory)\"](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))\n\nWhat is distance? The distance between two vertices $x$ and $y$ is the minimum number of edges one has to traverse to get from $x$ to $y$.\n\n## Constraints\n\n*   $1 \\leq N,K \\leq 10^5$\n*   $1 \\leq a_i,b_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$.$\n$.$\n$.$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc133_e","tags":[],"sample_group":[["4 3\n1 2\n2 3\n3 4","6\n\n![image](https://img.atcoder.jp/ghi/491cd56a53e99ba7677ee4827b8f767a.png)\nThere are six ways to paint the tree."],["5 4\n1 2\n1 3\n1 4\n4 5","48"],["16 22\n12 1\n3 1\n4 16\n7 12\n6 2\n2 15\n5 16\n14 16\n10 11\n3 10\n3 13\n8 6\n16 8\n9 12\n4 3","271414432"]],"created_at":"2026-03-03 11:01:14"}}