{"problem":{"name":"[DTCPC 2024] 人赢的跳棋","description":{"content":"给一棵 $n$ 个点的树，边有边权，边权为三元组。第 $i$ 条边的三元组 $e$ 为 $(e_{i,1},e_{i,2},e_{i,3})$。 设函数 $\\operatorname{win}(x,y)$： - 若 $x_2<y_2$ 且 $x_3<y_3$ 则 $\\operatorname{win}(x,y)=x_1$。 - 若 $x_2>y_2$ 且 $x_3>y_3$ 则  $\\opera","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10165"},"statements":[{"statement_type":"Markdown","content":"给一棵 $n$ 个点的树，边有边权，边权为三元组。第 $i$ 条边的三元组 $e$ 为 $(e_{i,1},e_{i,2},e_{i,3})$。\n\n设函数 $\\operatorname{win}(x,y)$：\n- 若 $x_2<y_2$ 且 $x_3<y_3$ 则 $\\operatorname{win}(x,y)=x_1$。\n- 若 $x_2>y_2$ 且 $x_3>y_3$ 则  $\\operatorname{win}(x,y)=y_1$ \n- 否则 $\\operatorname{win}(x,y)=0$。\n\n其中 $x=(x_1,x_2,x_3),y=(y_1,y_2,y_3)$。\n\n显然 $\\operatorname{win}$ 函数满足交换律。\n\n设一个三元组序列 $\\{a_n\\}$ 的权值为 $\\max_{i=1}^{n-1} \\operatorname{win}(a_i,a_{i+1})$，特别的，$n=1$ 时权值为 $0$。\n\n设一条路径的权值为经过的所有边的权值按顺序组成的序列的权值。\n\n求树的所有无向路径的权值和。\n\n## Input\n\n第一行一个正整数 $n$（$1 \\le n\\leq 3\\times 10^5$） 表示树的节点数。\n\n之后 $n-1$ 行每行四个整数表示 $u,v,e_{i,1},e_{i,2}$，其中有 $e_{i,3}=i$。\n\n保证 $\\{e_{i,1}\\}$ 互不相同，$\\{e_{i,2}\\}$ 互不相同，值域都为 $[1,n]$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n小 C 是人赢。\n\n每周三晚上，小 T 晚上在吃猪脚饭，小 C 晚上和妹子在食堂共进晚餐。\n\n每周五晚上，小 T 启动废墟图书馆，小 C 在和妹子聊天。\n\n今天小 T 在睡觉，而小 C 在和妹子玩人赢的跳棋。\n\n## Note\n\n2025/10/31 增加 hack 数据一组","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10165","tags":["2024","洛谷月赛"],"sample_group":[["5\n1 2 1 2\n1 3 2 1\n1 4 3 3\n1 5 4 4\n","9"],["7\n1 2 3 4\n2 3 6 2\n2 4 1 3\n2 5 4 6\n3 6 2 1\n5 7 5 5","44"]],"created_at":"2026-03-03 11:09:25"}}