wordpress 美化网站,wordpress配置qq邮件,社交网络的推广方法有哪些,网站兼容问题[ABC266F] Well-defined Path Queries on a Namori 题面翻译 题目描述 给定一张有 N N N 个点、 N N N 条边的简单连通无向图和 Q Q Q 次询问#xff0c;对于每次询问#xff0c;给定 x i , y i x_i,y_i xi,yi#xff0c;表示两点的编号#xff0c;请你回答第 x i … [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_iv_i \le N 1≤uivi≤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≤xiyi≤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
#includebits/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[oo1];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,i1;in;i){cin x y;add(x,y);add(y,x);}functionvoid(int,itn)dfs1[](itn x,itn fat){if(vis[x]){int nowx; is[x]1; xtag[x];while(now!x){is[x]1;xtag[x];}return void();} vis[x]1;for(int ihead[x];i;ist[i].nxt){int yst[i].v;if(yfat) continue;tag[y]x; dfs1(y,x);} };functionvoid(int,int)dfs2[](int x,int fat){if(!is[x]) fa[x]fa[fat];for(int ihead[x];i;ist[i].nxt){int yst[i].v;if(yfat||is[y]) continue;dfs2(y,x);}}; dfs1(1,0);for(int i1;in;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 $ 列目、$ l1 $ 列目、$ \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];
vectorint 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
#includebits/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 xy;}
struct nod{itn v,w,nxt;}st[oo1];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 i1;in;i) cind[i];for(int x,y,z,i1;in;i){cin x y z;add(x,y,z);add(y,x,z);}functionvoid(itn,int)dfs[](int x,int fa){for(int ihead[x];i;ist[i].nxt){int vst[i].v;if(vfa) continue;dfs(v,x); g[x]f[v];}int k0;for(int ihead[x];i;ist[i].nxt){int v st[i].v;if(v!fa) mx[k]g[v]st[i].w-f[v];}sort(mx1,mxk1,cmp);for(int i1;id[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 i1;ik;i) mx[i]0;};dfs(1,0);cout f[1] \n flush;exit (0);
}考虑树上DP在每个点枚举向父亲连边或向儿子连边
结合贪心优先选大边权的同时不选负边权的
