题目: http://codeforces.com/contest/1189/problem/D1
题意: 给定一棵树, 可以选择任意两个叶子节点对他们的路径增加一定的权值.
问对于给定的这棵树, 是否可以得到任意形式的权值.
思路:
只要有一个节点的度是 2, 那么这个节点连接的某一条边一定受到另一条边的控制.
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #define inf 0x3f3f3f3f
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pr;
- int n;
- const int maxn = 1e5 + 5;
- int deg[maxn];
- int main()
- {
- scanf("%d", &n);;
- for(int i = 1; i < n; i++){
- int u, v;
- scanf("%d%d", &u, &v);
- deg[u]++;
- deg[v]++;
- }
- int ans = true;
- for(int i = 1; i <= n; i++){
- if(deg[i] == 2){
- ans = false;
- break;
- }
- }
- if(ans){
- printf("YES\n");
- }
- else{
- printf("NO\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3118024.html