hdu5664(点分治+容斥+树状数组)

题解

很牛逼的点分啊 !!!!!

我们考虑二分答案 然后直接点分统计大于等于k的点对个数 复杂度$(O(nlog^2nlogw))$ 据说卡卡常数肯定是能过的 但是我们主要用下面这种方法

我们对于当前重心的子树节点按照点到重心的距离排序 因为点只有$nlogn$个 (点分的性质) 所以预处理复杂度$O(nlog^2n)$ 其次因为你在直接计算的过程中包含了不经过当前重心的点对 所以我们需要去重 同时记录当前重心直接儿子的子树情况 做一个容斥即可..

对于每一个二分的值 我们用双指针去统计贡献 则check复杂度为$O(nlogn)$

对于题目另外一个条件 需要满足去掉”直链” 所以我们直接在以m为根的树中把存在$lca(u,v)=u||lca(u,v)=v$的点对删掉即可

所以总复杂度$O(nlognlogw)$

代码实现

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e6+10;
const int NM=2e6+10;
const double eps=1e-8;
const int inf=1e9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n,m;ll k;
int sz[MAXN],maxx[MAXN],key,rt,base,dep[MAXN];
bool vis[MAXN];


inline void get_root(int x,int pre){
    sz[x]=1;maxx[x]=0;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	get_root(j->t,x);
	sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
    }
    maxx[x]=max(maxx[x],base-sz[x]);
    if(key>maxx[x])key=maxx[x],rt=x;
}

int L[MAXN],R[MAXN],tot;
int dis[MAXN],st[NM];
vector<pii>vec[MAXN];

inline void _dfs(int x,int pre){
    st[tot]=dis[x];tot++;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	dis[j->t]=dis[x]+j->v;
	_dfs(j->t,x);
    }
}
int tot1,St[NM];
inline void __dfs(int x,int pre){
    St[tot1]=dis[x];tot1++;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	__dfs(j->t,x);
    }
}
inline void solve(int x){
    vis[x]=1;L[x]=tot;st[tot]=0;tot++;
    link(x){
	if(vis[j->t])continue;
	dis[j->t]=j->v;_dfs(j->t,x);
    }
    R[x]=tot-1;sort(st+L[x],st+R[x]+1);
    link(x){
	if(vis[j->t])continue;
	pii t;t.first=tot1;__dfs(j->t,x);
	t.second=tot1-1;
	sort(St+t.first,St+t.second+1);
	vec[x].pb(t);
	key=inf;base=sz[j->t];get_root(j->t,0);
	solve(rt);
    }
}

inline ll calc(int l,int r,int x){
    if(l>=r)return 0;
    ll ans=0;
    int i=l;int j=r;
    while(i<j){
	while(i<j&&st[i]+st[j]>=x)ans+=r-j,j--;
	if(i<j)ans+=max(0,r-j);
	i++;
    }
    ans+=r-j;
    return ans;
}
inline ll calc1(int l,int r,int x){
    if(l>=r)return 0;
    ll ans=0;
    int i=l;int j=r;
    while(i<j){
	while(i<j&&St[i]+St[j]>=x)ans+=r-j,j--;
	if(i<j)ans+=max(0,r-j);
	i++;
    }
    ans+=r-j;
    return ans;
}

vector<int>v1;
int d[NM];
void dfs(int x,int pre,int y){
    v1.pb(d[x]);v1.pb(d[x]-y);
    link(x){
	if(j->t==pre)continue;
	d[j->t]=d[x]+j->v;
	dfs(j->t,x,y);
    }
}

int ans1,T;
int sum[NM];
int get_id(int x){return x&(-x);}
int Get_id(int x){
    return lower_bound(v1.begin(),v1.begin()+T,x)-v1.begin()+1;
}
void update(int x,int y){
    for(int i=x;i<=T;i+=get_id(i))sum[i]+=y;
}
int query(int x){
    int ans=0;
    for(int i=x;i>0;i-=get_id(i))ans+=sum[i];
    return ans;
}

void get_sum(int x,int pre,int y){
    ans1+=query(Get_id(d[x]-y));update(Get_id(d[x]),1);
    link(x){
	if(j->t==pre)continue;
	get_sum(j->t,x,y);
    }
    update(Get_id(d[x]),-1);
}

inline bool check(int x){
    ll ans=0;v1.clear();
    inc(i,1,n){
	ans+=calc(L[i],R[i],x);int size=vec[i].size();
	for(int j=0;j<size;j++){
	    int t1=vec[i][j].first;int t2=vec[i][j].second;
	    ans-=calc1(t1,t2,x);
	}
    }
    dfs(m,0,x);sort(v1.begin(),v1.end());
    T=unique(v1.begin(),v1.end())-v1.begin();
    ans1=0;get_sum(m,0,x);ans-=ans1;
    if(ans>=k)return 1;
    return 0;
}

int main(){
    int _=read();
    while(_--){
	tot=tot1=1;memset(h,0,sizeof(h));o=e;
	n=read();m=read();k=read();
	int x,y,z;
	inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
	key=inf;base=n;get_root(1,0);
	solve(rt);
	int l=1;int r=6e8;int ans=0;
	while(l<=r){
	    int mid=(l+r)>>1;
	    if(check(mid))ans=mid,l=mid+1;
	    else r=mid-1;
	}
	if(!ans)puts("NO");
	else printf("%d\n",ans);
	inc(i,1,n)vec[i].clear(),vis[i]=0,d[i]=L[i]=R[i]=0;
    }
    return 0;
}

题目描述

Lady CA has a tree with n points numbered $1,2,…,n$, and each edge has its weight. The unique route connecting two points is called a chain, and the length of a chain equals the sum value of the weights of the edges passed.

The point number m is called the root. Lady CA defines a special kind of chain called folded chain, the chain connecting the points numbered $x,y(x≠y)$ is called a folded chain, if and only if the chain connecting the point numbered $x$ and the root doesn’t pass the point numbered $y$, and the chain connecting the point numbered yand the root doesn’t pass the point numbered $x$.

Lady CA wants to find the length of the $kth$ longest folded chain. Notice that the chain connecting the points numbered $x,y$ and the chain connecting the points numbered $y$,$x$ are the same.

Input

The first line contains an integer $T(1≤T≤3)$——The number of the test cases. For each test case:
The first line contains three integers $n(2≤n≤50,000),m(1≤m≤n),k(1≤k≤n×(n−1)/2)$. Between each two adjacent integers there is a white space separated.
The second line to the nth line describes the $n−1$ edges in the graph. Each line contains three integers $u,v(1≤u,v≤n,u≠v),w(1≤w≤10,000)$, which means there is an edge which has a weight $w$ connecting the points numbered $u,v$. Between each two adjacent integers there is a white space separated.

Output

For each test case, the only line contains the only integer that is the length of the $kth$ longest folded chain. If the $kth$ longest folded chain doesn’t exist, print $NO$.