nocriz的博客

苔花如米小,也学牡丹开。

【NOI2018】情报中心

挖一个坑,待补题解。下附代码。

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>


using namespace std;
#define int ll
typedef long long ll;
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

ll chkmax(ll &a,ll b){return a = a>b?a:b;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> VI;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
	read(first);
	read(args...);
}

const int N = 100010;
int n,m,k,s[N],t[N],co[N],lc[N],u[N],v[N],w[N];
vector<int> G[N],G2[N],T[N];
struct work{
	int depth;
	ll ca,cb;
};
vector<work> E[N];
map<pii,int> dis;

ll d1[N];
int d[N];
int fa[N][19],dfn[N],sz[N],hom[N],seq[N],tim = 0,tim2 = 0;

namespace rmq {
	const int MAXN = 1e5 + 5;
	const int MAXLOG = 18;
	int mi[MAXN][MAXLOG], lg[MAXN];
	#define cmp(x,y) ((d[x] < d[y]) ? x : y)
	inline int qmin(int l, int r) {
		if(l>r)swap(l,r);
		int tmp = lg[r - l + 1];
		return cmp(mi[l][tmp], mi[r - (1 << tmp) + 1][tmp]);
	}
	void init(int *a, int n) {
		for (int i = 1; i <= n; i++) {
			mi[i][0] = a[i];
			lg[i] = lg[i - 1] + ((1 << (lg[i-1] + 1)) <= i);
		}
		for (int t = 1; t < MAXLOG; t++)
		for (int i = 1, j = (1 << (t - 1)) + 1; j <= n; i++, j++)
			mi[i][t] = cmp(mi[i][t - 1], mi[j][t - 1]);
	}
}

void dfs0(int num,int cf = 0){
	dfn[num] = ++tim;
	hom[num] = ++tim2;seq[tim2] = num;
	sz[num] = 1;
	for(auto ct:G[num]){
		if(ct==cf)continue;
		d1[ct] = d1[num]+dis[MP(num,ct)];
		d[ct] = d[num]+1;
		dfs0(ct,num);
		seq[++tim2] = num;
		sz[num]+=sz[ct];
	}
}

inline int lca(int u,int v){
	return rmq::qmin(hom[u],hom[v]);
}
inline ll dist(int u,int v){
	return d1[u]+d1[v]-2*d1[lca(u,v)];
}
vector<pii> F[N];

struct node{
	int ls,rs;
	ll ma,mb;
}nds[10000010];
int cnt = 0,rts[N];

#define mid ((cl+cr)/2)
int newnode(){
	++cnt;
	nds[cnt].ls = nds[cnt].rs = 0;
	nds[cnt].ma = nds[cnt].mb = -1e18;
	return cnt;
}
void mrg(int id){
	chkmax(nds[id].ma,max(nds[nds[id].ls].ma,nds[nds[id].rs].ma));
	chkmax(nds[id].mb,max(nds[nds[id].ls].mb,nds[nds[id].rs].mb));
}
void destroy(int &id,int x,int cl = 0,int cr = n){
	if(!id)return;
	if(cl == cr){
		nds[id].ma = nds[id].mb = -1e18;
		return;
	}
	if(x<=mid)destroy(nds[id].ls,x,cl,mid);
	else destroy(nds[id].rs,x,mid+1,cr);
	nds[id].ma = max(nds[nds[id].ls].ma,nds[nds[id].rs].ma);
	nds[id].mb = max(nds[nds[id].ls].mb,nds[nds[id].rs].mb);
}
void add(int &id,int x,ll va,ll vb,ll &cval,int cl = 0,int cr = n){
	if(!id)id = newnode();
	chkmax(nds[id].ma,va);
	chkmax(nds[id].mb,vb);
	if(cl == cr)return;
	if(x<=mid){
		add(nds[id].ls,x,va,vb,cval,cl,mid);
		chkmax(cval,va+nds[nds[id].rs].mb);
	}else{
		add(nds[id].rs,x,va,vb,cval,mid+1,cr);
		chkmax(cval,vb+nds[nds[id].ls].ma);
	}
}
int merge(int a,int b,ll &cval){
	if(!a || !b)return a|b;
	chkmax(cval,nds[nds[a].ls].ma+nds[nds[b].rs].mb);
	chkmax(cval,nds[nds[b].ls].ma+nds[nds[a].rs].mb);
	chkmax(nds[a].ma,nds[b].ma);chkmax(nds[a].mb,nds[b].mb);
	nds[a].ls = merge(nds[a].ls,nds[b].ls,cval);
	nds[a].rs = merge(nds[a].rs,nds[b].rs,cval);
	return a;
}
ll ans = -1e18;
int crt = 0;
void dfs(int num,int f = 0){
	ll cval = -1e18;
	for(auto ct:E[num]){
		add(rts[num],ct.depth,ct.ca,ct.cb,cval);
	}
	for(auto ct:G[num]){
		if(ct == f)continue;
		dfs(ct,num);
		merge(rts[num],rts[ct],cval);
	}
	ans = max(ans,cval-d1[num]);
	destroy(rts[num],d[num]-1);
}

struct Mp{
	int po = -1;
	ll coef = -1e18;
	Mp(){}
	Mp(int a,ll b):po(a),coef(b){}
};
struct Pp{
	Mp A,B;
	Pp(){}
	Pp(Mp A,Mp B):A(A),B(B){}
	ll dis(){
		if(A.po == -1 || B.po == -1){
			return A.coef+B.coef;
		}
		return dist(A.po,B.po)+A.coef+B.coef;
	}
};
Pp dfs1(int num){
	Pp ret,nret;
	auto chk = [&](Pp a){
		if(a.dis()>nret.dis())nret = a;
	};
	for(auto ct:T[num]){
		int nt = num^s[ct]^t[ct];
		ll coef = dist(num,nt)-2*co[ct]+d1[num];
		chk(Pp(ret.A,Mp(nt,coef)));
		chk(Pp(ret.B,Mp(nt,coef)));
		ret = nret;
	}
	if(num!=crt)ans = max(ans,nret.dis()/2-d1[num]);
	for(auto ech:G2[num]){
		Pp ct = dfs1(ech);
		nret = Pp();
		chk(Pp(ret.A,ct.A));
		chk(Pp(ret.A,ct.B));
		chk(Pp(ret.B,ct.A));
		chk(Pp(ret.B,ct.B));
		if(num!=crt)ans = max(ans,nret.dis()/2-d1[num]);
		chk(ret);
		chk(ct);
		ret = nret;
	}
	return ret;
}

void solve(){
	read(n);
	for(int i=1;i<n;i++){
		read(u[i],v[i],w[i]);
		G[u[i]].PB(v[i]);
		G[v[i]].PB(u[i]);
		dis[MP(u[i],v[i])] = w[i];
		dis[MP(v[i],u[i])] = w[i];
	}
	d[1] = 1;
	dfs0(1);
	rmq::init(seq,tim2);
	read(m);
	for(int i=0;i<m;i++){
		read(s[i],t[i],co[i]);
		lc[i] = lca(s[i],t[i]);
		ll da = dist(s[i],t[i])-co[i],db = da+d1[lc[i]];
		if(s[i]!=lc[i])E[s[i]].push_back({d[lc[i]],da,db});
		if(t[i]!=lc[i])E[t[i]].push_back({d[lc[i]],da,db});
		F[lc[i]].emplace_back(s[i],i);
		F[lc[i]].emplace_back(t[i],i);
	}
	for(int i=1;i<=n;i++)rts[i] = newnode();
	dfs(1);
	auto cmp = [&](int a,int b)->bool{return dfn[a]<dfn[b];};
	
	for(int i=1;i<=n;i++){
		crt = i;
		vector<int> cu,scope;
		scope.PB(i);
		for(auto ct:F[i]){
			cu.PB(ct.F);
			T[ct.F].PB(ct.S);
		}
		sort(all(cu),cmp);
		cu.erase(unique(all(cu)),cu.end());
		vector<int> stk;
		stk.PB(i);
		rts[i] = newnode();
		auto pb = [&](int a){
			rts[a] = newnode();
			scope.PB(a);
			stk.PB(a);
		};
		for(auto ct:cu){
			int dd = lca(ct,stk.back());
			while(d[stk.back()]>d[dd]){
				if(d[stk[stk.size()-2]]>d[dd]) G2[stk[stk.size()-2]].PB(stk.back());
				else G2[dd].PB(stk.back());
				stk.pop_back();
			}
			if(d[stk.back()]<d[dd]) pb(dd);
			if(d[stk.back()]<d[ct]) pb(ct);
		}
		while(stk.size()>=2){
			G2[stk[stk.size()-2]].PB(stk.back());
			stk.pop_back();
		}
		dfs1(i);
		for(auto ct:scope){
			G2[ct].clear();
			rts[ct] = 0;
			T[ct].clear();
		}
	}
}

void clear(){
	if(ans<-1e16) cout<<"F\n";
	else cout<<ans<<"\n";
	for(int i=1;i<=n;i++){
		E[i].clear();
		F[i].clear();
		G[i].clear();
	}
	cnt = 0;
	dis.clear();
	tim = tim2 = 0;
	ans = -1e18;
}
signed main() {
	nds[0].ma = nds[0].mb = -1e18;
	int testcases;
	read(testcases);
	while(testcases--){
		solve();
		clear();
	}
	return 0;
}

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注