深圳企业网站建设价格,深圳网络营销运营,网页设计论文的研究内容,国外优秀网页设计网站Codeforces Round #520 (Div. 2) D. Fun with Integers 题意#xff1a;a与b之间有边#xff0c;当且仅当存在一个\(x\)使得\(a*b x\)或 \(a*x b\)#xff0c;这条边的边权为\(|x|\)#xff0c;保证\(|a|,|b|,|x|n\)#xff0c;问一条最长的不走重复边的路径的长度是… Codeforces Round #520 (Div. 2) D. Fun with Integers 题意a与b之间有边当且仅当存在一个\(x\)使得\(a*b x\)或 \(a*x b\)这条边的边权为\(|x|\)保证\(|a|,|b|,|x|n\)问一条最长的不走重复边的路径的长度是多少。 做法对于一个数\(a\)如果存在一个\(b\)与他相连那么一定存在一个\(-b\)与他相连可以知道每个点的度数一定是偶数。那么一定存在欧拉回路因此将所有边去啊即求和即可。 #include bits/stdc.h
#define pb push_back
typedef long long ll;
using namespace std;
int n;
ll ans;
int main() {scanf(%d,n);for(int i 2; i n; i)for(int jii;jn;ji) ans j/i;printf(%lld\n,ans2LL);return 0;
} E. Company 题意给定一棵树q次询问每次询问编号在 [l,r] 区间内的点删除其中哪一个点使得lca的深度最深。 做法一个区间的lca一定时这个区间内dfs序编号最小和最大之间的lca那么删除的点也一定是这两个点钟的一个。因此求dfs序之后st表维护区间最值即可。 #include bits/stdc.h
#define pb push_back
typedef long long ll;
using namespace std;
int n, q;
vectorint G[100055];
int id, ind[100055], fid[100055], dep[100055], fa[100055][22];
void dfs(int u,int pre) {ind[u] id; fid[id] u; fa[u][0] pre;for(int j1;j20;j) fa[u][j] fa[fa[u][j-1]][j-1];for(int i 0; i G[u].size(); i) {int v G[u][i];dep[v] dep[u] 1; dfs(v,u);}
}
int mx[100055][22], mn[100055][22], Log[100055];
void init_rmq() {Log[1] 0;for(int i 2; i n; i) Log[i] Log[i1] 1;for(int i 1; i n; i) mx[i][0] mn[i][0] ind[i];for(int i 1; i 20; i) for(int j 1; j (1(i-1)) n; j) {mx[j][i] max(mx[j][i-1], mx[j(1(i-1))][i-1]);mn[j][i] min(mn[j][i-1], mn[j(1(i-1))][i-1]);}
}
int ask_mn(int l,int r) {int L Log[r-l1];return min(mn[l][L], mn[r-(1L)1][L]);
}
int ask_mx(int l,int r) {int L Log[r-l1];return max(mx[l][L], mx[r-(1L)1][L]);
}
int lca(int u,int v) {if(dep[u] dep[v]) swap(u,v);int tx u, ty v;for(int ddep[v]-dep[u],i0;d;d1,i) if(d1) ty fa[ty][i];if(tx ty) return tx;for(int i 20; i 0; --i) {if(fa[tx][i] fa[ty][i]) continue;tx fa[tx][i], ty fa[ty][i];}return fa[tx][0];
}
int fd_fa(int x,int l,int r) {int u1, v1;if(x l) u1 ask_mn(l1,r), v1 ask_mx(l1,r);else if(x r) u1 ask_mn(l,r-1), v1 ask_mx(l,r-1);else {u1 min(ask_mn(l,x-1), ask_mn(x1,r));v1 max(ask_mx(l,x-1), ask_mx(x1,r));}return lca(fid[u1],fid[v1]);
}
int main() {scanf(%d%d,n,q);for(int p,i 2; i n; i) scanf(%d,p), G[p].pb(i);dfs(1,0); init_rmq();while(q--) {int l, r;scanf(%d%d,l,r);if(n 2) { printf(1 1\n); continue; }int ld ask_mn(l,r), rd ask_mx(l,r);int fa1 fd_fa(fid[ld],l,r), fa2 fd_fa(fid[rd],l,r);if(dep[fa1] dep[fa2]) printf(%d %d\n,fid[ld],dep[fa1]);else printf(%d %d\n,fid[rd],dep[fa2]);}return 0;
} 转载于:https://www.cnblogs.com/RRRR-wys/p/9969807.html
