网站收录地址,旅游网站建设的相关报价,建材网站的模板,wordpress火吗VJ地址
题意#xff1a;给一个有根树给你#xff0c;计算一下满足下列条件的序列对的数目 #xff08;1#xff09;u是v的祖先#xff08;不能是它自己#xff09; #xff08;2#xff09;a[v]*a[u]k
思路#xff1a;用DFS序分裂每一条链#xff0c;使链上的点…VJ地址
题意给一个有根树给你计算一下满足下列条件的序列对的数目 1u是v的祖先不能是它自己 2a[v]*a[u]k
思路用DFS序分裂每一条链使链上的点都是当前加入点的祖先用树状数组维护or线段树因为是单点修改就用就树状数组了。 每次加入点前计算小于等于k/a[v]点的数量。还有数据大小是1e9但是只有1e5个点要离散化处理。
ps还有要自己找到根节点。
具体细节
#pragma comment(linker, /STACK:1024000000,1024000000)
#include bits/stdc.h
#define INF 2e18
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1e97;
const ll N 2e510;
const double eps 1e-4;
const double piacos(-1);
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
using namespace std;
vectorint g[N];
ll n,k;
ll a[N];
ll lsh[N];
ll sum;
ll cnt;
ll c[N];
int vis[N];
ll getid(ll x)
{return lower_bound(lsh1,lshcnt1,x)-lsh;
}
void add(ll x,ll v)
{while(xN){c[x]v;xlowbit(x);}
}
ll query(ll x)
{ll ans0;while(x){ansc[x];x-lowbit(x);}return ans;
}
void dfs(int u,int p){add(getid(a[u]),1);for(int v:g[u]){if(vp) continue;sumquery(getid(k/a[v]1)-1);dfs(v,u);}add(getid(a[u]),-1);
}
void sovle(){sum0;cinnk;FILL(c,0);FILL(vis,0);for(int i1;in;i) {cina[i];lsh[i]a[i];}sort(lsh1,lsh1n);cntunique(lsh1,lshn1)-lsh-1;for(int i1;in;i){int u,v;cinuv;g[u].push_back(v);g[v].push_back(u);vis[v]1;}for(int i1;in;i){if(!vis[i]) {dfs(i,0);break;}}coutsumendl;for(int i1;in;i) g[i].clear();
}
int main()
{iosint t1;cint;while(t--){sovle();}return 0;
}
