你有一棵nn n个节点的树，根节点为1，定义好的路径是连接祖先节点和其子孙节点的路径 如图，路径(1,5)(1,5) (1,5)是好的路径，因为节点11 1是节点55 5的祖先 路径(6,4)(6,4) (6,4)不是好的路径，因为节点66 6不是节点44 4的祖先，节点44 4也不是节点66 6的祖先 你希望知道有多少对路径{(a,b),(c,d)}lbrace (a,b),
你有一棵n n n 个节点的树，根节点为1，定义好的路径是连接祖先节点和其子孙节点的路径 如图，路径(1,5) (1,5) (1,5) 是好的路径，因为节点1 1 1 是节点5 5 5 的祖先 路径(6,4) (6,4) (6,4) 不是好的路径，因为节点6 6 6 不是节点4 4 4 的祖先，节点4 4 4 也不是节点6 6 6 的祖先 你希望知道有多少对路径{(a,b),(c,d)}lbrace (a,b),(c,d) rbrace{(a,b),(c,d)}满足(a,b) (a,b) (a,b) 和(c,d) (c,d) (c,d) 的路径交是长度在[l,r]lbrack l,r rbrack[l,r]之间的好的路径 下面是一些你可能会用到的定义: 路径交:(a,b),(c,d) (a,b) , (c,d) (a,b),(c,d) 的路径交定义为路径(a,b) (a,b) (a,b) 和(c,d) (c,d) (c,d) 路径所共同覆盖的点和边(可能为空） 不难看出一对路径的交还是一条路径 路径长度：路径上边的数量 路径(a,b) (a,b) (a,b) 和(b,a) (b,a) (b,a) 视为同一条 路径对{(a,b),(c,d)}lbrace (a,b),(c,d)rbrace{(a,b),(c,d)}与{(c,d),(a,b)}lbrace (c,d),(a,b) rbrace{(c,d),(a,b)}视为同一对 路径对{(a,b),(a,b)}lbrace (a,b),(a,b) rbrace{(a,b),(a,b)}不计入答案
标签： HBC19186树题解
