2024.9.19

[ABC266F] Well-defined Path Queries on a Namori

题面翻译

题目描述

给定一张有 $N$ 个点、$N$ 条边的简单连通无向图和 $Q$ 次询问，对于每次询问，给定 $x_i,y_i$，表示两点的编号，请你回答第 $x_i$ 个点和第 $y_i$ 个点之间是否有且仅有一条简单路径。

• 什么是简单路径？

如果路径上的各顶点均不重复，则称这样的路径为简单路径。

输入格式

第一行包含一个整数 $N$；

接下来 $N$ 行，每行两个整数 $u_i,v_i$，表示第 $i$ 条边连接的两个点；

再接下来一行包含一个整数 $Q$；

最后 $Q$ 行，每行两个整数 $x_i,y_i$，含义见题目描述。

输出格式

对于每次询问，输出一个字符串 Yes 或 No，分别表示两点之间是否仅存在一条简单路径，每个询问分别输出一行。

样例

见原题面。

样例解析

样例 #1 解析：

对于第一次询问，从 $1$ 到 $2$ 有两条简单路径 $(1,2)$、$(1,3,2)$，所以输出 No。

对于第二次询问，从 $1$ 到 $4$ 仅有一条路径 $(1,4)$，所以输出 Yes。

对于第三次询问，从 $1$ 到 $5$ 有两条简单路径 $(1,2,5)$、$(1,3,2,5)$，所以输出 No。

数据范围

对于 $30\%$ 的数据，$N\le 100$，$Q\le \frac{N(N-1)}{2}$；

对于 $100\%$ 的数据，$3\le N\le 2\times 10^5$，$1\le u_i<v_i\le N$，$1\le Q\le 2\times 10^5$，$1\le x_i<y_i\le N$，保证图没有重边或自环，且给定询问均不重复。

翻译 by @CarroT1212

题目描述

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ N $ 辺の連結な単純無向グラフ $ G $ が与えられます。$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます。

以下の $ Q $ 個のクエリに答えてください。

• 頂点 $ x_i $ から頂点 $ y_i $ に向かう単純パス（同じ頂点を $ 2 $ 度通らないパス）が一意に定まるか判定せよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_N $ $ v_N $ $ Q $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_Q $ $ y_Q $

输出格式

$ Q $ 行出力せよ。

$ i\ (1\ \leq\ i\ \leq\ Q) $ 行目には、頂点 $ x_i $ から頂点 $ y_i $ に向かう単純パスが一意に定まる場合 Yes、そうでない場合 No を出力せよ。

样例 #1

样例输入 #1

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

样例输出 #1

No
Yes
No

样例 #2

样例输入 #2

10
3 5
5 7
4 8
2 9
1 2
7 9
1 6
4 10
2 5
2 10
10
1 8
6 9
8 10
6 8
3 10
3 9
1 10
5 8
1 10
7 8

样例输出 #2

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No

提示

制約

• $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
• $ 1\ \leq\ u_i\ <\ v_i\leq\ N $
• $ i\ \neq\ j $ ならば $ (u_i,v_i)\ \neq\ (u_j,v_j) $
• $ G $ は $ N $ 頂点 $ N $ 辺の連結な単純無向グラフ
• $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $
• $ 1\ \leq\ x_i\ <\ y_i\leq\ N $
• 入力は全て整数

Sample Explanation 1

頂点 $ 1 $ から $ 2 $ に向かう単純パスは $ (1,2),(1,3,2) $ と一意に定まらないので、 $ 1 $ 個目のクエリの答えは No です。 頂点 $ 1 $ から $ 4 $ に向かう単純パスは $ (1,4) $ と一意に定まるので、$ 2 $ 個目のクエリの答えは Yes です。 頂点 $ 1 $ から $ 5 $ に向かう単純パスは $ (1,2,5),(1,3,2,5) $ と一意に定まらないので、$ 3 $ 個目のクエリの答えは No です。

//2024.9.19
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 200005;
int n,q;int tag[oo],fa[oo];
bool vis[oo],is[oo];
struct nod{int v,nxt;}st[oo<<1];int head[oo],cnt;
__inline void add(int x,int y){st[++cnt]=(nod){y,head[x]};head[x]=cnt;}
main(void){//fre();cin.tie(0)->sync_with_stdio(0);cin >> n;for(int x,y,i=1;i<=n;++i){cin >> x >> y;add(x,y);add(y,x);}function<void(int,itn)>dfs1=[&](itn x,itn fat){if(vis[x]){int now=x; is[x]=1; x=tag[x];while(now!=x){is[x]=1;x=tag[x];}return void();} vis[x]=1;for(int i=head[x];i;i=st[i].nxt){int y=st[i].v;if(y==fat) continue;tag[y]=x; dfs1(y,x);}   };function<void(int,int)>dfs2=[&](int x,int fat){if(!is[x]) fa[x]=fa[fat];for(int i=head[x];i;i=st[i].nxt){int y=st[i].v;if(y==fat||is[y]) continue;dfs2(y,x);}}; dfs1(1,0);for(int i=1;i<=n;++i) if(is[i]){fa[i]=i;dfs2(i,0);}cin >> q;while(q--){int x,y;cin >> x >> y;cout << (fa[x]==fa[y]?"Yes":"No") << '\n';} cout << flush;exit (0);
}

直接在基环树上dfs，直接记录在环上各个点上分支的父亲即可

---

[ABC253F] Operations on a Matrix

题面翻译

存在 $ n $ 行 $ m $ 列的矩阵，给定 $ q $ 次操作，有 $ 3 $ 种格式。

• 1 l r x：将 $ [l, r] $ 列的所有元素全部加上 $ x $。
• 2 i x：将第 $ i $ 行的元素全部变为 $ x $。
• 3 i j：输出矩阵 $ (i, j) $ 位置的元素值。

题目描述

縦 $ N $ 行、横 $ M $ 列の行列があり、はじめ全ての成分は $ 0 $ です。

以下のいずれかの形式で表されるクエリを $ Q $ 個処理してください。

• 1 l r x : $ l $ 列目、$ l+1 $ 列目、$ \ldots $、$ r $ 列目の成分全てに $ x $ を足す。
• 2 i x : $ i $ 行目の成分全てを $ x $ で置き換える。
• 3 i j : $ (i,\ j) $ 成分を出力する。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ Q $ $ \mathrm{Query}_1 $ $ \vdots $ $ \mathrm{Query}_Q $

$ i $ 番目に与えられるクエリを表す $ \mathrm{Query}_i $ は以下のいずれかの形式である。

$ 1 $ $ l $ $ r $ $ x $

$ 2 $ $ i $ $ x $

$ 3 $ $ i $ $ j $

输出格式

3 i j の形式の各クエリについて、答えを一行に出力せよ。

样例 #1

样例输入 #1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

样例输出 #1

1
2
2
5
3
4

样例 #2

样例输入 #2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

样例输出 #2

9000000000

样例 #3

样例输入 #3

10 10 10
1 1 8 5
2 2 6
3 2 1
3 4 7
1 5 9 7
3 3 2
3 2 8
2 8 10
3 8 8
3 1 10

样例输出 #3

6
5
5
13
10
0

提示

制約

• $ 1\ \leq\ N,\ M,\ Q\ \leq\ 2\ \times\ 10^5 $
• 1 l r x の形式のクエリについて、$ 1\ \leq\ l\ \leq\ r\ \leq\ M $ かつ $ 1\ \leq\ x\ \leq\ 10^9 $
• 2 i x の形式のクエリについて、$ 1\ \leq\ i\ \leq\ N $ かつ $ 1\ \leq\ x\ \leq\ 10^9 $
• 3 i j の形式にクエリについて、$ 1\ \leq\ i\ \leq\ N $ かつ $ 1\ \leq\ j\ \leq\ M $
• 3 i j の形式のクエリが一個以上与えられる
• 入力は全て整数

Sample Explanation 1

行列は次のように変化します。 $ \begin{pmatrix}\ 0\ &\ 0\ &\ 0\ \ 0\ &\ 0\ &\ 0\ \ 0\ &\ 0\ &\ 0\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ 2\ &\ 2\ &\ 2\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 4\ &\ 3\ \ 1\ &\ 4\ &\ 3\ \ 2\ &\ 5\ &\ 5\ \ \end{pmatrix} $

#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) (x & -x)
using namespace std;const int N = 200010;int n, m, Q, last[N];
LL tr[N], ans[N];
vector<int> v[N];struct query {int op, a, b, c;
} q[N];void add(int x, int c)
{for(int i = x; i <= m; i += lowbit(i)) tr[i] += c;
}LL sum(int x)
{LL res = 0;for(int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}int main()
{cin >> n >> m >> Q;for(int i = 1; i <= Q; i++) {scanf("%d%d%d", &q[i].op, &q[i].a, &q[i].b);if(q[i].op == 1) scanf("%d", &q[i].c);else if(q[i].op == 2) last[q[i].a] = i;else v[last[q[i].a]].push_back(i);}for(int i = 1; i <= Q; i++) {if(q[i].op == 1) add(q[i].a, q[i].c), add(q[i].b + 1, -q[i].c);else if(q[i].op == 2) for(auto item : v[i]) ans[item] = q[i].b - sum(q[item].b);  else printf("%lld\n", ans[i] + sum(q[i].b));}return 0;
}

多板的主席树题呢

---

[ABC259F] Select Edges

题面翻译

给定一棵 $n$ 个节点的树，每条边有一个权值 $w_i$。

现要求选择一些边，使得每个节点 $i$ 相邻的边中被选中的不超过 $d_i$ 条，请求出最大边权和。

题目描述

$ N $ 頂点の木が与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ重み $ w_i $ の辺です。

$ N-1 $ 本の辺のうちのいくつか（ $ 0 $ 本または $ N-1 $ 本すべてでも良い）を選ぶことを考えます。 ただし、$ i\ =\ 1,\ 2,\ \ldots,\ N $ について、頂点 $ i $ に接続する辺は $ d_i $ 本までしか選べません。 選ぶ辺の重みの総和としてあり得る最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ d_1 $ $ d_2 $ $ \ldots $ $ d_N $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ w_{N-1} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

7
1 2 1 0 2 1 1
1 2 8
2 3 9
2 4 10
2 5 -3
5 6 8
5 7 3

样例输出 #1

28

样例 #2

样例输入 #2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

样例输出 #2

2184

提示

制約

• $ 2\ \leq\ N\ \leq\ 3\ \times\ 10^5 $
• $ 1\ \leq\ u_i,\ v_i\ \leq\ N $
• $ -10^{9 \leq w_i \leq 10}9 $
• $ d_i $ は頂点 $ i $ の次数以下の非負整数
• 与えられるグラフは木である
• 入力はすべて整数

Sample Explanation 1

$ 1,\ 2,\ 5,\ 6 $ 番目の辺を選ぶと、選ぶ辺の重みは $ 8\ +\ 9\ +\ 8\ +\ 3\ =\ 28 $ となります。これがあり得る最大値です。

//2024.9.19
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr int oo = 300005;
int n,k;int d[oo];
itn mx[oo],f[oo],g[oo];
int cmp(itn x,itn y){return x>y;}
struct nod{itn v,w,nxt;}st[oo<<1];int cnt,head[oo];
__inline void add(int x,int y,itn z){st[++cnt]=(nod){y,z,head[x]};head[x]=cnt;}
main(void){//fre();cin.tie(0)->ios::sync_with_stdio(0);cin >> n;for(int i=1;i<=n;i++) cin>>d[i];for(int x,y,z,i=1;i<n;i++){cin >> x >> y >> z;add(x,y,z);add(y,x,z);}function<void(itn,int)>dfs=[&](int x,int fa){for(int i=head[x];i;i=st[i].nxt){int v=st[i].v;if(v==fa) continue;dfs(v,x); g[x]+=f[v];}int k=0;for(int i=head[x];i;i=st[i].nxt){int v = st[i].v;if(v!=fa) mx[++k]=g[v]+st[i].w-f[v];}sort(mx+1,mx+k+1,cmp);for(int i=1;i<d[x];i++){if(mx[i]<=0) break;g[x]+=mx[i];}f[x] = g[x];if(mx[d[x]]>0) f[x]+=mx[d[x]];if(!d[x]) g[x] = -1e9;for(int i=1;i<=k;i++) mx[i]=0;};dfs(1,0);cout << f[1] << '\n' << flush;exit (0);
}

考虑树上DP，在每个点枚举向父亲连边或向儿子连边

结合贪心，优先选大边权的，同时不选负边权的