acwing_xyy

$$\large\mathrm{青涩の醉挽清风Team}$$ $$\href{https://www.acwing.com/blog/content/26205/}{\huge {个人主页}}$$

2.2万

xcb
mofa世界大magua

F_

wujiay
itdef
Hexicam

yangaich

ZZMQ
xyh不是xyy

# [NOIP2015 提高组] 运输计划

## 题目描述

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

## 样例 #1

### 样例输入 #1

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5


### 样例输出 #1

11


## 提示

### 算法1

#### C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 300010, M = N * 2, K = 20;

{
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
return s * w;
}

typedef long long LL;

struct Edge
{
int a, b, w;
}edge[N], query[N];

int n, m, p[N];
int h[N], e[M], w[M], ne[M], idx;
int d[N];
LL dist[N], res, q_dist[N];
int fa[N][K];
int f[N];
int q[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
int hh = 0, tt = 0;
q[0] = 1;
d[1] = 1;

while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];

if (d[j]) continue;

d[j] = d[t] + 1;
dist[j] = dist[t] + w[i];

fa[j][0] = t;
for (int k = 1; k <= 19; k ++ ) fa[j][k] = fa[fa[j][k - 1]][k - 1];

q[ ++ tt] = j;
}
}
}

int lca(int a, int b)
{
if (d[a] < d[b]) swap(a, b);

for (int i = 19; i >= 0; i -- )
if (d[fa[a][i]] >= d[b])
a = fa[a][i];
if (a == b) return a;

for (int i = 19; i >= 0; i -- )
if (fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}

void dfs(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;

dfs(j, u);

f[u] += f[j];
}
}

LL get_dist(int a, int b) //树上两点距离
{
return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

bool check(LL mid)
{
memset(f, 0, sizeof f);

int cnt = 0;
LL maxd = 0;
for (int i = 1; i <= m; i ++ )
{
int a = query[i].a, b = query[i].b;
if (q_dist[i] > mid)
{
cnt ++ ;
f[a] ++ , f[b] ++ , f[p[i]] -= 2; //树上差分
maxd = max(maxd, q_dist[i]);
}
}

dfs(1, -1);

for (int i = 1; i < n; i ++ )
{
int a = edge[i].a, b = edge[i].b;
if (d[a] < d[b]) swap(a, b);

if (f[a] == cnt && maxd - edge[i].w <= mid) return true;
}

return false;
}

int main()
{
memset(h, -1, sizeof h);

for (int i = 1; i < n; i ++ )
{
int a, b, c;

edge[i] = {a, b, c};
}

bfs(); //倍增LCA

for (int i = 1; i <= m; i ++ )
{
int a, b;

query[i] = {a, b};
q_dist[i] = get_dist(a, b);
p[i] = lca(a, b);
//printf("%lld\n", get_dist(a, b));
}

LL l = 0, r = 1e18;
while (l < r) //二分答案
{
LL mid = l + r >> 1;

if (check(mid)) r = mid;
else l = mid + 1;
}

printf("%lld\n", r);

return 0;
}


# [NOIP2014 提高组] 联合权值

## 样例 #1

### 样例输入 #1

5
1 2
2 3
3 4
4 5
1 5 2 3 10


### 样例输出 #1

20 74


## 提示

【数据说明】

### 算法1

#### 首先，距离为2的点对有两种

• 该结点和他父亲的父亲结点，即该节点和他的爷爷
• 该结点和他的兄弟结点

#### C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2000010, mod = 10007;

typedef long long LL;

int n, w[N];
LL tot[N], maxx[N][2];
int h[N], e[N * 2], ne[N * 2], idx;
int d[N], fa[N][2];
int q[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
int hh = 0, tt = 0;
q[0] = 1;
d[1] = 1;

while (hh <= tt)
{
int t = q[hh ++ ];

for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];

if (d[j]) continue;

tot[t] += w[j]; //总权值
if (w[j] > maxx[t][0]) //最大值和次大值
{
maxx[t][1] = maxx[t][0];
maxx[t][0] = w[j];
} else if (w[j] > maxx[t][1]) maxx[t][1] = w[j];

d[j] = d[t] + 1;
fa[j][0] = t, fa[j][1] = fa[t][0]; //父亲结点和爷爷结点

q[ ++ tt] = j;
}
}
}

int main()
{
memset(h, -1, sizeof h);
scanf("%d", &n);

for (int i = 1; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);

}
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

bfs();

LL res = 0;
for (int i = 1; i <= n; i ++ ) //第一种情况
if (fa[i][1])
res = max(res, (LL)w[i] * w[fa[i][1]]);
for (int i = 1; i <= n; i ++ ) //第二种情况
if (fa[i][0])
{
if (w[i] == maxx[fa[i][0]][0]) res = max(res, w[i] * maxx[fa[i][0]][1]); //该节点是最大值，改用次大值
else res = max(res, w[i] * maxx[fa[i][0]][0]);
}

printf("%lld ", res);

res = 0;
for (int i = 1; i <= n; i ++ )
if (fa[i][1])
res = (res + (LL)w[i] * w[fa[i][1]] % mod) % mod;
res = res * 2 % mod;
for (int i = 1; i <= n; i ++ )
if (fa[i][0])
res = (res + (LL)w[i] * (tot[fa[i][0]] - w[i]) % mod) % mod;
printf("%lld\n", res);

return 0;
}


class Solution {
public:
void sortColors(vector<int>& nums) {
vector<int> count(3, 0);

for (int i = 0; i < nums.size(); i ++ ) count[nums[i]] ++ ;

for (int i = 0, t = 0; i < 3; i ++ )
for (int j = 0; j < count[i]; j ++ )
nums[t ++ ] = i;
}
};


class Solution {
public:
string simplifyPath(string path) {
string res, name;
if (path.back() != '/') path += '/';

for (auto c : path) {
if (c != '/') name += c;
else {
if (name == "..") {
while (res.size() && res.back() != '/') res.pop_back();
if (res.size()) res.pop_back();
}
else if (name != "." && name != "") {
res += '/' + name;
}
name.clear();
}
}

if (res.empty()) res = "/";
return res;
}
};


class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
if (!n || !m) return n + m;

vector<vector<int>> f(n + 1, vector<int>(m + 1));

f[0][0] = 0;
for (int i = 1; i <= n; i ++ ) f[i][0] = i;
for (int j = 1; j <= m; j ++ ) f[0][j] = j;

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j - 1] +
(word1[i - 1] != word2[j - 1]);
f[i][j] = min(f[i][j], f[i - 1][j] + 1);
f[i][j] = min(f[i][j], f[i][j - 1] + 1);
}
return f[n][m];
}
};


class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();

vector<bool> row(m), col(n);

for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
if (!matrix[i][j])
row[i] = col[j] = true;

for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
if (row[i] | col[j])
matrix[i][j] = 0;
}
};


class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;

int n = matrix.size(), m = matrix[0].size();
int l = 0, r = n * m - 1;

while (l < r)
{
int mid = l + r >> 1;

if (matrix[mid / m][mid % m] >= target) r = mid;
else l = mid + 1;
}

return matrix[r / m][r % m] == target;
}
};


class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hash;
int cnt = 0;

for (auto c : t)
{
if (!hash[c]) cnt ++ ;
hash[c] ++ ;
}

string res = "";
for (int i = 0, j = 0, c = 0; i < s.size(); i ++ )
{
if (hash[s[i]] == 1) c ++ ;
hash[s[i]] -- ;
while (c == cnt && hash[s[j]] < 0) hash[s[j ++ ]] ++ ;

if (c == cnt)
{
if (res.empty() || res.size() > i - j + 1)
res = s.substr(j, i - j + 1);
}
}

return res;
}
};


class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(int u, int last, int& n, int& k)
{
if (u == k)
{
res.push_back(path);
return ;
}

for (int i = last + 1; i <= n; i ++ )
{
path.push_back(i);
dfs(u + 1, i, n, k);
path.pop_back();
}
}

vector<vector<int>> combine(int n, int k) {

dfs(0, 0, n, k);
return res;
}
};