[USACO23OPEN] Triples of Cows P

Luogu

IDLGP9194

Time2000ms

Memory256MB

DifficultyP7

数学USACO并查集2023仙人掌圆方树

There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\dots N$, forming a tree. The cows are leaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the farm, and then all pairs of the $i$ th cow's friends still present on the farm become friends. For each $i$ from $1$ to $N$, just before the $i$ th cow leaves, how many ordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$ are on vacation, $a$ is friends with $b$, and $b$ is friends with $c$? ## Input The first line contains $N$. The next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows $u_i$ and $v_i$ are initially friends. ## Output The answers for $i$ from $1$ to $N$ on separate lines. [samples] ## Note For the first sample: $(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves. After cow $1$ leaves, there are less than $3$ cows left, so no triples are possible. For the second sample: At the beginning, cow $1$ is friends with all other cows, and no other pairs of cows are friends, so the triples are $(a, 1, c)$ where $a, c$ are different cows from $\{2, 3, 4\}$, which gives $3 \cdot 2 = 6$ triples. After cow $1$ leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the $3! = 6$ possible orders. After cow $2$ leaves, there are less than $3$ cows left, so no triples are possible. $2\le N\le 2\cdot 10^5$, $1\le u_i,v_i\le N$. - Inputs 4-5: $N\le 500$. - Inputs 6-10: $N\le 5000$. - Inputs 11-20: No additional constraints.

Samples

Input #1

3
1 2
2 3

Output #1

2
0
0

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO23OPEN] Triples of Cows P",
    "description": {
      "content": "There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\\dots N$, forming a tree. The cows are leaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the farm, an",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9194"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\\dots N$, forming a tree. The cows are\nleaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the\nfarm, an...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments