2024.9.19
[ABC266F] Well-defined Path Queries on a Namori
题面翻译
题目描述
给定一张有 N N N 个点、 N N N 条边的简单连通无向图和 Q Q Q 次询问，对于每次询问，给定 x i , y i x_i,y_i xi,yi，表示两点的编号，请你回答第 x i x_i xi 个点和第 y i y_i yi 个点之间是否有且仅有一条简单路径。
- 什么是简单路径？
如果路径上的各顶点均不重复，则称这样的路径为简单路径。
输入格式
第一行包含一个整数 N N N；
接下来 N N N 行，每行两个整数 u i , v i u_i,v_i ui,vi，表示第 i i i 条边连接的两个点；
再接下来一行包含一个整数 Q Q Q；
最后 Q Q Q 行，每行两个整数 x i , y i x_i,y_i xi,yi，含义见题目描述。
输出格式
对于每次询问，输出一个字符串
Yes或No，分别表示两点之间是否仅存在一条简单路径，每个询问分别输出一行。样例
见原题面。
样例解析
样例 #1 解析：
对于第一次询问，从 1 1 1 到 2 2 2 有两条简单路径 ( 1 , 2 ) (1,2) (1,2)、 ( 1 , 3 , 2 ) (1,3,2) (1,3,2)，所以输出
No。对于第二次询问，从 1 1 1 到 4 4 4 仅有一条路径 ( 1 , 4 ) (1,4) (1,4)，所以输出
Yes。对于第三次询问，从 1 1 1 到 5 5 5 有两条简单路径 ( 1 , 2 , 5 ) (1,2,5) (1,2,5)、 ( 1 , 3 , 2 , 5 ) (1,3,2,5) (1,3,2,5)，所以输出
No。数据范围
对于 30 % 30\% 30% 的数据， N ≤ 100 N \le 100 N≤100， Q ≤ N ( N − 1 ) 2 Q \le \frac{N(N-1)}{2} Q≤2N(N−1)；
对于 100 % 100\% 100% 的数据， 3 ≤ N ≤ 2 × 1 0 5 3 \le N \le 2 \times 10^5 3≤N≤2×105， 1 ≤ u i < v i ≤ N 1 \le u_i<v_i \le N 1≤ui<vi≤N， 1 ≤ Q ≤ 2 × 1 0 5 1 \le Q \le 2 \times 10^5 1≤Q≤2×105， 1 ≤ x i < y i ≤ N 1 \le x_i < y_i \le N 1≤xi<yi≤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 n n 个节点的树，每条边有一个权值 w i w_i wi。
现要求选择一些边，使得每个节点 i i i 相邻的边中被选中的不超过 d i d_i di 条，请求出最大边权和。
题目描述
$ 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 $
- $ -109 \leq w_i \leq 109 $
- $ 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，在每个点枚举向父亲连边或向儿子连边
结合贪心，优先选大边权的，同时不选负边权的