Fire

C++14(g++5.4) 解法, 执行用时: 185ms, 内存消耗: 27460K, 提交时间: 2020-01-14 22:38:16

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

ostream& operator<<(ostream& os, const pair<char, int>& unit) {
  return os << unit.first << "^" << unit.second;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 100010;

int n, k;
int a[N], s[N];
ll x[N], y[N];
vector<int> g[N];
vector<pair<pair<ll, int>, int>> greedy[N];

void dfs(int u) {
  s[u] = 1;
  for (int v : g[u])
    if (!s[v]) {
      dfs(v);
      s[u] += s[v];
      greedy[u].emplace_back(make_pair(x[v] - 1, s[v] * 2), v);
    }
  sort(greedy[u].begin(), greedy[u].end(), [&](const pair<pair<ll, int>, int>& lhs, const pair<pair<ll, int>, int>& rhs) { return rhs.first.first - lhs.first.second > lhs.first.first - rhs.first.second; });
  int d = greedy[u].size();
  vector<ll> dp;
  dp.push_back(numeric_limits<ll>::max());
  int pre = 0;
  x[u] = a[u] + min(k - 2 * s[u], 0);
  for (const auto& pr : greedy[u]) {
    x[u] = min(x[u], pr.first.first - pre);
    dp.push_back(min(dp.back(), pr.first.first - pre));
    pre += pr.first.second;
  }
  if (d) {
    vector<ll> suf(d + 1);
    suf[d] = numeric_limits<ll>::max();
    for (int i = d - 1; i >= 0; --i)
      suf[i] = min(suf[i + 1] - greedy[u][i].first.second, greedy[u][i].first.first);
    y[u] = numeric_limits<ll>::min();
    pre = 0;
    for (int i = 0; i < d; ++i) {
      int v = greedy[u][i].second;
      //cerr << k << ' ' << (s[u] - s[v]) << ' ' << d << '\n';
      //cerr << "=> " << v << ": " << (y[v] - 2 * (s[u] - s[v] - 1) - 1) << ' ' << (suf[i + 1] - pre) << ' ' << dp[i] << ' ' << a[u] << ' ' << (a[u] + k - 2 * (s[u] - s[v])) << '\n';
      y[u] = max(y[u], min({y[v] - 2 * (s[u] - s[v] - 1) - 1, suf[i + 1] - pre, dp[i], (ll)a[u], a[u] + k - 2LL * (s[u] - s[v])}));
      pre += greedy[u][i].first.second;
    }
  } else
    y[u] = a[u];
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  for (int rep = 1; rep < n; ++rep) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) cin >> a[i];
  dfs(1);
//  cerr << y[1] << '\n';
  cout << max(-1LL, y[1]) << '\n';

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

C++ 解法, 执行用时: 90ms, 内存消耗: 12980K, 提交时间: 2022-07-14 23:47:27

#include<cstdio>
#include<algorithm>
using namespace std;
int n,nex[200001],fir[100001],sto[200001],ui,vi,tot,fa[100001],sz[100001],cnt;
long long f[200001][2],a[200001],k,pre[200001],las[200001],b[200001],s,ans;
struct node{long long v;int num;};
node c[200001];
bool cmp(node aa,node bb){return(aa.v>bb.v);}
void addbian(int aa,int bb)
{
	tot++;
	sto[tot]=bb;
	nex[tot]=fir[aa];
	fir[aa]=tot;
}
long long getmin(long long aa,long long bb)
{
	if(aa<bb)return(aa);
	else return(bb);
}
long long getmax(long long aa,long long bb)
{
	if(aa<bb)return(bb);
	else return(aa);
}
void dfs(int x)
{
	int aa=fir[x];
	sz[x]=1;
	while(aa!=0)
	{
		if(sto[aa]!=fa[x])
		{
			fa[sto[aa]]=x;
			dfs(sto[aa]);
			sz[x]=sz[x]+sz[sto[aa]]; 
		}
		aa=nex[aa];
	}
	f[x][0]=getmin(a[x],a[x]+k-2*sz[x]);
	f[x][1]=a[x];
	cnt=0;
	aa=fir[x];
	while(aa!=0)
	{
		if(sto[aa]!=fa[x])
		{
			cnt++;
			c[cnt].num=sto[aa];
			c[cnt].v=f[sto[aa]][0]-2*(sz[x]-sz[sto[aa]]-1)-1;
		}
		aa=nex[aa];
	}
	if(cnt!=0)
	{
		sort(c+1,c+1+cnt,cmp);
		las[cnt+1]=1000000000000000000;
		pre[0]=1000000000000000000;
		s=0;
		for(int i=1;i<=cnt;i++)
		{
			b[i]=c[i].v+2*s;
			s=s+sz[c[i].num];
			pre[i]=getmin(pre[i-1],b[i]);
			f[x][0]=getmin(f[x][0],b[i]);
		}
		f[x][1]=-10000000000;
		for(int i=cnt;i>=1;i--)las[i]=getmin(las[i+1],b[i]);
		for(int i=1;i<=cnt;i++)f[x][1]=getmax(f[x][1],getmin(getmin(f[c[i].num][1]-2*(sz[x]-sz[c[i].num]-1)-1,a[x]+k-2*(sz[x]-sz[c[i].num])),getmin(pre[i-1]+2*sz[c[i].num],las[i+1])));
		f[x][1]=getmin(f[x][1],a[x]);
	}
}
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)fir[i]=0;
	tot=0;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&ui,&vi);
		addbian(ui,vi);
		addbian(vi,ui);
	}
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	fa[1]=1;
	dfs(1);
	ans=getmax(f[1][0],f[1][1]);
	printf("%d\n",getmax(-1,ans));
}

详情