[Ynoi2003] 戌亥彗星

Luogu

IDLGP8531

Time9000ms

Memory512MB

DifficultyP7

2003O2优化Ynoi

定义一个图为海胆，如果它满足以下条件： 1. 是一个连通图 2. 包含恰好一个简单环 3. 除了环以外的点每个点度数不超过 $2$ 有一张图，有 $n$ 个点，$n$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$（不保证联通）。定义一张图的区间子图 $[l,r]$ 为 $(V',E'),E'=\{(u_i,v_i)|l\leq i\leq r\},V'=\{u_i|l\leq i\leq r\} \cup \{v_i|l\leq i\leq r\}$，也就是说，这个区间子图包含且仅包含区间中的边和所有在区间中一条边上的点。现在有 $q$ 次询问，每次给定一个区间 $l,r$，求 $l,r$ 有多少个子区间 $[l',r'](l\leq l'\leq r'\leq r)$ 满足原图的 $[l',r']$ 区间子图是个海胆。 **对于条件 2 的补充说明：** 1. 简单环的定义是可以从任一点开始经过一些不重复的边回到起点，途中经过了至少一条边，且除了起点和终点相同以外不经过重复点，例如 $1-2-3-1$ 是简单环，两条 $1-2$ 的边是简单环，但只有一个点的时候不是, $1-2-3-4-5-3-1$ 也不是，（这里的环用某一个点开始的路径表示）。 2. 条件 $2$ 要求除了环边以外不存在边两端都在这个环上。 ## Input 第一行一个整数 $n$，表示点数和边数。接下来 $n$ 行，每行两个整数 $u_i,v_i$ 表示一条边。接下来一行一个整数 $q$。接下来 $q$ 行，每行两个整数 $l,r$ 表示一个询问。 ## Output $q$ 行，每行一个数表示这组询问的答案。 [samples] ## Note Idea：lk&nzhtl1477，Solution：lk&ccz181078，Code：lk&ccz181078，Data：lk&ccz181078 **数据保证不存在自环** | 子任务编号 | $n\le$ | $q\le$ | 特殊性质 | 分值 | | :--------: | :-----: | :-----: | :------------: | :---: | | $1$ | $100$ | $100$ | 无 | $5$ | | $2$ | $500$ | $500$ | 无 | $15$ | | $3$ | $5000$ | $5000$ | 无 | $15 $ | | $4$ | $50000$ | $50000$ | 无 | $15$ | | $5$ | $10^6$ | $1$ | 无 | $15 $ | | $6$ | $10^6$ | $10^6$ | 原图是一个海胆 | $15$ | | $7$ | $10^6$ | $10^6$ | 无 | $20$ |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi2003] 戌亥彗星",
    "description": {
      "content": "定义一个图为海胆， 如果它满足以下条件： 1. 是一个连通图 2. 包含恰好一个简单环 3. 除了环以外的点每个点度数不超过 $2$ 有一张图，有 $n$ 个点，$n$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$（不保证联通）。 定义一张图的区间子图 $[l,r]$ 为 $(V',E'),E'=\\{(u_i,v_i)|l\\leq i\\leq r\\},V'=\\{u_i|l\\leq ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 9000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8531"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义一个图为海胆， 如果它满足以下条件：\n\n1. 是一个连通图\n2. 包含恰好一个简单环\n3. 除了环以外的点每个点度数不超过 $2$\n\n有一张图，有 $n$ 个点，$n$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$（不保证联通）。\n\n定义一张图的区间子图 $[l,r]$ 为 $(V',E'),E'=\\{(u_i,v_i)|l\\leq i\\leq r\\},V'=\\{u_i|l\\leq ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments