C. Xor in Tree

Codeforces

IDCF10240C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Diego has a tree with exactly $N$ nodes, numbered from $1$ to $N$, where every edge is bidirectional and has an arbitrary number $X$ written on it. Diego is wondering for every unordered pair or nodes (i,j) within the tree what is the sum of the exclusive ors between the path of nodes (i,j). For this problem a path between two nodes is a simple path (no cycles) and also the shortest path between said nodes. Just to be clear, he wants to know: $\\sum_{i = 1}^{N} \\sum_{j = i + 1}^{N} P (i, j)$ Where $P (a, b)$ represents the exclusive or of every edge within the path of node a to node b. An integer N $(1 <= N <= 10^5)$, the amount of nodes in the tree that Diego has. Followed by $N -1$ lines, each line comes in the format u v X $(1 <= u, v <= N, u eq.not v, 1 <= X <= 10^9)$, which indicates that there is a bidirectional edge between nodes u and v which has value $X$ written on it. It is guaranteed that the input will be a tree. A single integer, the sum of the exclusive or between the path of every unordered pair of nodes. If you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition. ## Input An integer N $(1 <= N <= 10^5)$, the amount of nodes in the tree that Diego has. Followed by $N -1$ lines, each line comes in the format u v X $(1 <= u, v <= N, u eq.not v, 1 <= X <= 10^9)$, which indicates that there is a bidirectional edge between nodes u and v which has value $X$ written on it. It is guaranteed that the input will be a tree. ## Output A single integer, the sum of the exclusive or between the path of every unordered pair of nodes. [samples] ## Note If you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition.

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = N $, where each edge $ e \in E $ has a weight $ w(e) \in \mathbb{Z}^+ $. For any unordered pair of distinct nodes $ (i, j) $, let $ P(i, j) $ denote the XOR of all edge weights along the unique simple path between $ i $ and $ j $. **Constraints** 1. $ 1 \le N \le 10^5 $ 2. Each edge weight satisfies $ 1 \le w(e) \le 10^9 $ 3. The graph is a tree (connected, acyclic, $ |E| = N - 1 $) **Objective** Compute: $$ \sum_{1 \le i < j \le N} P(i, j) $$

API Response (JSON)

{
  "problem": {
    "name": "C. Xor in Tree",
    "description": {
      "content": "Diego has a tree with exactly $N$ nodes, numbered from $1$ to $N$, where every edge is bidirectional and has an arbitrary number $X$ written on it. Diego is wondering for every unordered pair or node",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10240C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Diego has a tree with exactly $N$ nodes, numbered from $1$ to $N$, where every edge is bidirectional and has an arbitrary number $X$ written on it.\n\nDiego is wondering for every unordered pair or node...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = N $, where each edge $ e \\in E $ has a weight $ w(e) \\in \\mathbb{Z}^+ $.  \nFor any unordered pair of distinct nodes $ (i, j) $, let $ P(i, j...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments