题目内容

请实现一个小型 PKI 证书签发点：证书构成森林（多棵树），边表示签发关系。吊销采用懒标记：只标记被吊销的那张证书；查询有效性时再沿父链检查。

请实现类 CertAuthority：

• CertAuthority()：初始化，当前没有任何证书。
• issue(int certId, int parentId, int expireAt)：签发证书。
  • certId 必须为正整数且尚未存在，否则返回 false
  • expireAt 必须为正整数，否则返回 false
  • parentId = 0 表示自签根证书
  • parentId ≠ 0 时：父证书必须已存在，且从父证书走到根的路径上没有任何已吊销节点；同时必须满足 expireAt ≤ 父证书的 expireAt（子证书不得比签发者活得更久）
  • 成功签发返回 true
• revoke(int certId)：吊销该证书（只标记自己，不遍历子孙）。
  • 证书不存在，或已经被吊销，返回 false
  • 否则标记成功，返回 true
• isValid(int certId, int now)：判断在时刻 now 是否有效。
  • 证书必须存在
  • 自身未被吊销，且 $now < \textit{expireAt}$
  • 从自身走到根，路径上每一张证书都满足上两条（祖先过期或被吊销，则后代无效）
  • 过期规则与「从这个时刻起失效」一致：$now \ge \textit{expireAt}$ 即过期
• ttl(int certId, int now)：若 isValid(certId, now) 为真，返回路径上最小 expireAt 减去 now（剩余有效时间）；否则返回 -1
• issuerOf(int certId)：返回父证书 id；根证书返回 0；不存在返回 -1（已被吊销仍算存在）
• rootOf(int certId)：沿父链走到根，返回根证书 id；不存在返回 -1

约束：累计调用 $\le 4000$；$1\le \textit{certId}\le 10^6$；parentId 为 $0$ 或合法证书编号；$1\le \textit{expireAt}\le 10^9$；$0\le \textit{now}\le 10^9$（非法参数由对应接口返回失败，不保证输入全合法）。

输入描述

每行一次函数调用，首行必为 CertAuthority()。

输出描述

每次调用一行：

• 构造输出 null
• issue / revoke / isValid 输出 true / false
• ttl / issuerOf / rootOf 输出整数

样例1

输入：

CertAuthority()
issue(1, 0, 100)
issue(2, 1, 80)
issue(3, 1, 120)
isValid(2, 50)
ttl(2, 50)
issue(3, 1, 60)
revoke(1)
isValid(2, 50)
isValid(1, 50)
ttl(3, 10)
issuerOf(2)
rootOf(3)
issue(4, 2, 50)

输出：

null
true
true
false
true
30
true
true
false
false
-1
1
1
false

说明：

• 根证书 $1$ 过期时刻 $100$，子证书 $2$ 为 $80$，合法
• $3$ 想活到 $120$，长过父证书，签发失败
• 时刻 $50$ 时 $2$ 仍有效，剩余 $\min(80,100)-50=30$
• 吊销根 $1$ 后，后代即使自身未标记吊销也全部无效；不能再挂在 $2$ 下面签发

样例2

输入：

CertAuthority()
issue(0, 0, 10)
issue(1, 2, 10)
issue(5, 0, 0)
issue(5, 0, 10)
issue(5, 0, 20)
revoke(9)
revoke(5)
revoke(5)
isValid(5, 0)
ttl(5, 0)
issuerOf(9)
rootOf(5)

输出：

null
false
false
false
true
false
false
true
false
false
-1
-1
5

说明：certId 必须为正；父节点必须已存在；expireAt 必须为正；重复签发失败；重复吊销失败；吊销后 rootOf 仍可查询。