METO CODE 223 拉力赛

2024-01-19 14:30
文章标签 code 223 meto 拉力赛

本文主要是介绍METO CODE 223 拉力赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

传送门

继续水板子题...

#include <bits/stdc++.h>
#define ll long long
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}const int maxn = 5e5 + 10;struct Edge { int to, next, c; } edge[maxn];
int cnt, head[maxn];
struct Qedge { int to, next; } qedge[maxn];
int qcnt, qhead[maxn], n, m;
int lca[maxn];
ll dep[maxn];
int par[maxn];
int temp[maxn];
bool vis[maxn];
inline void addedge(int u, int v, int c) {edge[++cnt].to = v;edge[cnt].c = c;edge[cnt].next = head[u];head[u] = cnt; 
}
inline void addqedge(int u, int v) {qedge[++qcnt].to = v;qedge[qcnt].next = qhead[u];qhead[u] = qcnt;
}
int getfa(int x) { return x == par[x] ? x : par[x] = getfa(par[x]); }void dfs(int u) {par[u] = u;vis[u] = 1; for (int i = head[u]; i; i = edge[i].next) {int v = edge[i].to;if (!vis[v]) {dep[v] = dep[u] + edge[i].c;dfs(v);par[v] = u;} }for (int i = qhead[u]; i; i = qedge[i].next) {int v = qedge[i].to;if (vis[v]) {lca[i] = getfa(v);if (i % 2) lca[i + 1] = lca[i];else lca[i-1] = lca[i];}}
}int main() {n = read(), m = read();for (int i = 0; i < n - 1; i++) {int u = read(), v =read(), c = read();addedge(u, v, c);addedge(v, u, c);} for (int i = 1; i <= m; i++) {int u = read(), v = read();addqedge(u, v), addqedge(v, u);}dfs(1);ll ans = 0;int cnt = 0;for (int i = 1; i <= m; i++) {if (lca[2 * i] == qedge[2 * i].to) {cnt++;ans += dep[qedge[2*i].to] + dep[qedge[2*i-1].to] - 2 * dep[lca[2*i]];}} printf("%d\n%lld\n", cnt, ans);return 0;
}
View Code

 

转载于:https://www.cnblogs.com/Mrzdtz220/p/10777236.html

这篇关于METO CODE 223 拉力赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/622715

相关文章

Debugging Lua Project created in Cocos Code IDE creates “Waiting for debugger to connect” in Win-7

转自 I Installed Cocos Code IDE and created a new Lua Project. When Debugging the Project(F11) the game window pops up and gives me the message waiting for debugger to connect and then freezes. Also a

LLVM入门2:如何基于自己的代码生成IR-LLVM IR code generation实例介绍

概述 本节将通过一个简单的例子来介绍如何生成llvm IR,以Kaleidoscope IR中的例子为例,我们基于LLVM接口构建一个简单的编译器,实现简单的语句解析并转化为LLVM IR,生成对应的LLVM IR部分,代码如下,文件名为toy.cpp,先给出代码,后面会详细介绍每一步分代码: #include "llvm/ADT/APFloat.h"#include "llvm/ADT/S

VS Code 调试go程序的相关配置说明

用 VS code 调试Go程序需要在.vscode/launch.json文件中增加如下配置:  // launch.json{// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information,

code: 400, msg: Required request body is missing 错误解决

引起这个错误的原因是,请求参数按照get方式给。 应该给json字符串才对 补充: 1. @RequestBody String resource 加@RequestBody必须给json字符串,否则会报错400,记如标题错误。 不加这个的进行请求的话,其实post和get就没有什么区别了。 2. List<String> indexCodes=(List<String>)json.

iOS项目发布提交出现invalid code signing entitlements错误。

1、进入开发者账号,选择App IDs,找到自己项目对应的AppId,点击进去编辑, 2、看下错误提示出现  --Specifically, value "CVYZ6723728.*" for key "com.apple.developer.ubiquity-container-identifiers" in XX is not supported.-- 这样的错误提示 将ubiquity

解决服务器VS Code中Jupyter突然崩溃的问题

问题 本来在服务器Anaconda的Python环境里装其他的包,装完了想在Jupyter里写代码验证一下有没有装好,一运行发现Jupyter崩溃了!?报错如下所示 Failed to start the Kernel. ImportError: /home/hujh/anaconda3/envs/mia/lib/python3.12/lib-dynload/_sqlite3.cpython-

Behind the Code:与 Rakic 和 Todorovic 对话 OriginTrail 如何实现 AI 去中心化

原文:https://www.youtube.com/watch?v=ZMuLyLCtE3s&list=PLtyd7v_I7PGnko80O0LCwQQsvhwAMu9cv&index=12 作者:The Kusamarian 编译:OneBlock+ 随着人工智能技术的飞速发展,一系列前所未有的挑战随之而来:模型的衰退与互联网的潜在威胁愈发明显。AI 的增长曲线可能因训练过程中的瓶颈而趋于平

冒泡排序和鸡尾酒排序(code)

昨天回顾了下冒泡排序和鸡尾酒排序,用面向对象的方式写了一下,并且优化了代码,记录一下~ 一、冒泡排序 # 冒泡排序class BubbleSort(object):def __init__(self, data_list):self.data_list = data_listself.length = len(data_list)# 简单粗暴的排序方式def b_sort(self):d

编译时出现错误 -- clang: error: linker command failed with exit code 1 (use -v to see invocation)

出现这个错误的原因有多种,常见的是因为某些文件的缺失或者是文件的重复导致的。 这类错误查看的关键在于其上一行的文字。 对于文件缺少而导致错误的情况: 例如上图中的示例,其上一行文字为 ld:library not found for -lrxl,可以看出是缺失了某一文件而导致的错误,这行文字中的最后“ -lrxl ”:-l 代表着其前缀是“lib”,连着后面的 rxl,其名称为 libr

GCDAsyncUdpSocket 使用时出现错误 Domain=NSPOSIXErrorDomain Code=13 Permission denied

完整的错误描述为: Domain=NSPOSIXErrorDomain Code=13 "Permission denied" UserInfo={NSLocalizedDescription=Permission denied, NSLocalizedFailureReason=Error in send() function.} 原始代码是这样的: clientBroadcast