NAIPC-2016

A. Fancy Antiques

爆搜+剪枝。

#include <bits/stdc++.h>
using namespace std ;

typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 105 ;
const int INF = 0x3f3f3f3f ;

struct Node {
	vector < pii > G ;
	int val ;
	bool operator < ( const Node& a ) const {
		return val > a.val ;
	}
} ;

Node a[MAXN] ;
int minv[MAXN][MAXN] ;
int pre[MAXN] ;
int tmp[MAXN][MAXN] ;
int ans ;
int n , m , k ;

void dfs ( int cur , int num ) {
	int val = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		if ( pre[i] == INF ) {
			val = INF ;
			break ;
		}
		val += pre[i] ;
	}
	if ( val < ans ) ans = val ;
	int tot = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		if ( pre[i] == INF && minv[cur][i] == INF ) return ;
		tot += min ( pre[i] , minv[cur][i] ) ;
	}
	if ( tot >= ans ) return ;
	if ( num >= k ) return ;
	for ( int i = cur ; i <= m ; ++ i ) {
		for ( int j = 1 ; j <= n ; ++ j ) {
			tmp[num][j] = pre[j] ;
		}
//		vector < pii > tmp ;
//		int c = 0 , v = 0 ;
/*
		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {
			int x = a[i].G[j].first ;
			tmp.push_back ( pii ( x , pre[x] ) ) ;
			if ( a[i].G[j].second < pre[x] ) {
				if ( pre[x] != INF ) v -= pre[x] ;
				else ++ c ;
				pre[x] = a[i].G[j].second ;
				v += pre[x] ;
			}
		}
*/
		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {
			int x = a[i].G[j].first ;
			pre[x] = min ( pre[x] , a[i].G[j].second ) ;
		}
		dfs ( i + 1 , num + 1 ) ;
		for ( int j = 1 ; j <= n ; ++ j ) {
			pre[j] = tmp[num][j] ;
			/*
			int x = tmp[j].first ;
			pre[x] = tmp[j].second ;
			*/
		}
	}
}

void solve () {
	ans = INF ;
	for ( int i = 1 ; i <= m ; ++ i ) {
		a[i].G.clear () ;
		a[i].val = 0 ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		int x , p , y , q ;
		scanf ( "%d%d%d%d" , &x , &p , &y , &q ) ;
		a[x].val ++ ;
		a[y].val ++ ;
		if ( p < q ) a[x].val += 2 ;
		else a[y].val += 2 ;
		a[x].G.push_back ( pii ( i , p ) ) ;
		a[y].G.push_back ( pii ( i , q ) ) ;
	}
	sort ( a + 1 , a + m + 1 ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		minv[m + 1][i] = INF ;
		pre[i] = INF ;
	}
	for ( int i = m ; i >= 1 ; -- i ) {
		for ( int j = 1 ; j <= n ; ++ j ) {
			minv[i][j] = minv[i + 1][j] ;
		}
		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {
			int x = a[i].G[j].first , v = a[i].G[j].second ;
			minv[i][x] = min ( minv[i][x] , v ) ;
		}
	}
	dfs ( 1 , 0 ) ;
	printf ( "%d\n" , ans == INF ? -1 : ans ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;
	return 0 ;
}

　　

B. Alternative Bracket Notation

模拟。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int Maxn=4040;
char s[Maxn];
int len1[Maxn],len2[Maxn],L[Maxn],R[Maxn];
int n;
int sta[Maxn];
int top;
int numlen[Maxn*20];
int main(){
	for(int i=1;i<Maxn*20;i++){
		numlen[i]=numlen[i/10]+1;
	}
	while(scanf("%s",s)!=EOF){
		n=strlen(s);
		for(int i=0;i<n;i++)len1[i]=len2[i]=1;
		while(1){
			top=0;
			int curlen=0;
			for(int i=0;i<n;i++){
				if(s[i]=='('){
					curlen+=len1[i]+len2[i]+2;
					L[i]=curlen;
					sta[top++]=i;
				}
				else{
					R[sta[top-1]]=curlen;
					top--;
				}
			}
			bool flag=1;
			for(int i=0;i<n;i++){
				if(s[i]!='(')continue;
				if(numlen[L[i]]!=len1[i]||numlen[R[i]]!=len2[i]){flag=0;}
				len1[i]=numlen[L[i]];
				len2[i]=numlen[R[i]];
			}
			if(flag)break;
		}
		for(int i=0;i<n;i++){
			if(s[i]=='('){
				printf("%d,%d:",L[i],R[i]);
			}
		}
		puts("");
	}
	return 0;
}

　　

C. Greetings!

$f[i][S]$表示$i$种信封覆盖$S$集合浪费的最少面积，枚举子集转移即可。

时间复杂度$O(k3^n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int N=15;
int n,m,i,j,k,S,a[N],b[N],c[N],A[1<<N],B[1<<N],D[1<<N];
ll C[1<<N],ans,f[16][1<<N],cost[1<<N],tmp;
inline void up(ll&a,ll b){if(a>b)a=b;}
int main(){
  scanf("%d%d",&n,&m);
  for(i=0;i<n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
  for(S=1;S<1<<n;S++){
    for(i=0;i<n;i++)if(S>>i&1){
      A[S]=max(A[S],a[i]);
      B[S]=max(B[S],b[i]);
      C[S]+=1LL*a[i]*b[i]*c[i];
      D[S]+=c[i];
    }
    cost[S]=1LL*A[S]*B[S]*D[S]-C[S];
  }
  for(i=0;i<=m;i++)for(j=0;j<1<<n;j++)f[i][j]=inf;
  up(f[0][0],0);
  for(i=1;i<=m;i++)for(j=0;j<1<<n;j++){
    tmp=inf;
    for(k=j;k;k=(k-1)&j)if(f[i-1][j-k]<inf){
      up(tmp,f[i-1][j-k]+cost[k]);
    }
    f[i][j]=tmp;
  }
  ans=inf;
  for(i=0;i<=m;i++)up(ans,f[i][(1<<n)-1]);
  printf("%lld",ans);
}

　　

D. Programming Team

0/1分数规划，二分比率，然后树形依赖背包DP即可，时间复杂度$O(n^2\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2502;
const double Inf=1e50;
int n,k;
double dp[2520][2520];
int s[Maxn],p[Maxn],id[Maxn];
int pre[Maxn],fin[Maxn];
vector<int>G[Maxn];
int dfs_t;
void dfs(int u){
	pre[u]=++dfs_t;
	id[dfs_t]=u;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		dfs(v);
	}
	fin[u]=dfs_t;
}
double check(double x){
	for(int i=1;i<=n+1;i++){
		for(int j=0;j<=k;j++){
			dp[i][j]=-1e60;
		}
	}
	dp[1][0]=0;
	for(int i=1;i<=n;i++){
		double w=p[id[i]]-s[id[i]]*x;
		for(int j=0;j<=k;j++){
			if(dp[i][j]<-Inf)continue;
			if(j<k){
				dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+w);
			}
			dp[fin[id[i]]+1][j]=max(dp[fin[id[i]]+1][j],dp[i][j]);
		}
	}
	return dp[n+1][k];
}
int main(){
	while(scanf("%d%d",&k,&n)!=EOF){
		for(int i=1;i<=n;i++)pre[i]=0,G[i].clear();
		for(int i=1;i<=n;i++){
			int f;
			scanf("%d%d%d",s+i,p+i,&f);
			G[f].push_back(i);
		}
		dfs_t=0;
		for(int i=1;i<=n;i++){
			if(!pre[i])dfs(i);
		}
		double l=0,r=10200;
		for(int i=0;i<30;i++){
			double mid=(l+r)/2.;
			double tp=check(mid);
			if(tp>0)l=mid;
			else r=mid;
		}
		printf("%.3f\n",r);
	}
}

　　

E. K-Inversions

构造多项式$A[i]=s[i]=='A'$，$B[n-i]=s[i]=='B'$，$C$为$A$和$B$的卷积，则答案就是$C[n+i]$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2200000;
int n,i,j,k;char s[N];
int pos[N];
struct comp{
  double r,i;
  comp(double _r=0,double _i=0){r=_r,i=_i;}
  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}
  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}
  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
  comp conj(){return comp(r,-i);}
}A[N],B[N];
const double pi=acos(-1.0);
void FFT(comp a[],int n,int t){
  for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
  for(int d=0;(1<<d)<n;d++){
    int m=1<<d,m2=m<<1;
    double o=pi*2/m2*t;comp _w(cos(o),sin(o));
    for(int i=0;i<n;i+=m2){
      comp w(1.0);
      for(int j=0;j<m;j++){
        comp&A=a[i+j+m],&B=a[i+j],t=w*A;
        A=B-t;B=B+t;w=w*_w;
      }
    }
  }
  if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;
}
int main(){
  scanf("%s",s+1);
  n=strlen(s+1);
  for(i=1;i<=n;i++)if(s[i]=='A')A[i].r=1;
  else A[n-i].i=1;
  k=1048576*2;
  j=__builtin_ctz(k)-1;
  for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);
  FFT(A,k,1);
  for(i=0;i<k;i++){
    j=(k-i)&(k-1);
    B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25);
  }
  FFT(B,k,-1);
  for(i=1;i<n;i++)printf("%d\n",(int)(B[i+n].r+0.5));
}

　　

F. Mountain Scenes

$f[i][j]$表示前$i$个数，和为$j$的方案数，时间复杂度$O(nwh)$。

#include<cstdio>
const int P=1000000007;
int n,w,h,i,j,k,ans,f[105][10005];
inline void up(int&x,int y){
  x+=y;
  if(x>=P)x-=P;
}
int main(){
  scanf("%d%d%d",&n,&w,&h);
  f[0][0]=1;
  for(i=1;i<=w;i++)
    for(j=0;j<=n;j++)if(f[i-1][j])
      for(k=0;k<=h;k++){
        if(j+k>n)break;
        up(f[i][j+k],f[i-1][j]);
      }
  for(i=0;i<=n;i++)up(ans,f[w][i]);
  for(i=0;i<=h;i++)if(i*w<=n)ans--;
  ans+=P;
  ans%=P;
  printf("%d",ans);
}

　　

G. Symmetry

枚举对称中心和对称轴，计算答案即可。时间复杂度$O(n^3)$。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
typedef pair < int , int > pii ;
typedef pair < LL , LL > pll ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 1005 ;

map < pii , int > mp1 ;
map < pair < pll , LL > , int > mp2 ;
map < pair < pll , LL > , int > mp3 ;

int x[MAXN] , y[MAXN] , num[MAXN * MAXN] ;
pii pt[MAXN * MAXN] ;
LL dis[MAXN][MAXN] ;
int n , p ;

pair < pll , LL > calc ( int x1 , int x2 , int y1 , int y2 ) {
	if ( x1 == x2 ) {
		LL A = 0 ;
		LL B = 1 ;
		LL C = - ( y1 + y2 ) / 2 ;
		return make_pair ( pii ( A , B ) , C ) ;
	}
	if ( y1 == y2 ) {
		LL A = 1 ;
		LL B = 0 ;
		LL C = - ( x1 + x2 ) / 2 ;
		return make_pair ( pii ( A , B ) , C ) ;
	}
	LL A = y2 - y1 ;
	LL B = x1 - x2 ;
	LL g = 0 ;
	LL C = - B * ( x1 + x2 ) / 2 + A * ( y1 + y2 ) / 2 ;
	swap ( A , B ) ;
	B = -B ;
	g = 0 ;
	if ( A ) {
		if ( A < 0 ) A = -A , B = -B , C = -C ;
	} else {
		if ( B < 0 ) A = -A , B = -B , C = -C ;
	}
	if ( A ) g = g ? __gcd ( g , abs ( A ) ) : abs ( A ) ;
	if ( B ) g = g ? __gcd ( g , abs ( B ) ) : abs ( B ) ;
	if ( C ) g = g ? __gcd ( g , abs ( C ) ) : abs ( C ) ;
	if ( g ) A /= g , B /= g , C /= g ;
	return make_pair ( pll ( A , B ) , C ) ;
}

int get_id ( pair < pll , LL > t ) {
	if ( mp2.count ( t ) ) return mp2[t] ;
	mp2[t] = ++ p ;
	num[p] = 0 ;
	return p ;
}

LL get_dis ( int x , int y ) {
	return 1LL * x * x + 1LL * y * y ;
}

void solve () {
	p = 0 ;
	mp1.clear () ;
	mp2.clear () ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%d%d" , &x[i] , &y[i] ) ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		for ( int j = 1 ; j <= n ; ++ j ) {
			dis[i][j] = get_dis ( x[i] - x[j] , y[i] - y[j] ) ;
		}
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		mp1[pii ( x[i] + x[i] , y[i] + y[i] )] ++ ;
		for ( int j = 1 ; j < i ; ++ j ) {
			mp1[pii ( x[i] + x[j] , y[i] + y[j] )] += 2 ;
			int id = get_id ( calc ( x[i] * 2 , x[j] * 2 , y[i] * 2 , y[j] * 2 ) ) ;
			num[id] += 2 ;
			pt[id] = pii ( i , j ) ;
		}
	}
	int ans = MAXN ;
	for ( map < pii , int > :: iterator it = mp1.begin () ; it != mp1.end () ; ++ it ) {
		ans = min ( ans , n - it->second ) ;
	}
	for ( int i = 1 ; i <= p ; ++ i ) {
		int xx = pt[i].first , yy = pt[i].second ;
		int cnt = 0 ;
		for ( int j = 1 ; j <= n ; ++ j ) {
			if ( dis[xx][j] == dis[yy][j] ) ++ cnt ;
		}
		ans = min ( ans , n - cnt - num[i] ) ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		for ( int j = 1 ; j <= n ; ++ j ) if ( i != j ) {
			LL A = y[j] - y[i] ;
			LL B = x[i] - x[j] ;
			LL C = x[j] * y[i] - x[i] * y[j] ;
			int cnt = 0 ;
			for ( int k = 1 ; k <= n ; ++ k ) {
				if ( A * x[k] + B * y[k] + C == 0 ) ++ cnt ;
			}
			ans = min ( ans , n - cnt ) ;
		}
	}
	printf ( "%d\n" , ans ) ;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

　　

H. Jewel Thief

$f[i][j]$表示考虑体积不超过$i$的物品，容量不超过$j$的最大收益。

对于当前体积$s$，将$j$按模$s$分组，每组转移满足决策单调性，分治求解即可。

时间复杂度$O(ks\log n)$。

#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=100010,M=1000010;
int n,m,i,j,k,w,x,y,o,q[N];ll f[N],g[N],v[M];
struct P{int x,y;}a[M];
inline bool cmp(const P&a,const P&b){return a.x==b.x?a.y>b.y:a.x<b.x;}
void solve(int l,int r,int dl,int dr){
  int m=(l+r)>>1,dm=dl;ll&d=g[m];d=0;
  for(int i=dl;i<=dr&&i<=m;i++){
    ll t=f[q[i]];
    if(m-i<=o)t+=v[m-i];
    if(t>d)d=t,dm=i;
  }
  if(l<m)solve(l,m-1,dl,dm);
  if(r>m)solve(m+1,r,dm,dr);
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
  std::sort(a+1,a+n+1,cmp);
  for(i=1;i<=n;i=j){
    w=a[i].x;
    if(w>m)break;
    for(j=i;j<=n&&a[i].x==a[j].x;j++)v[j-i+1]=v[j-i]+a[j].y;
    o=j-i;
    for(k=0;k<w;k++){
      for(x=k,y=0;x<=m;x+=w)q[++y]=x;
      solve(1,y,1,y);
      for(x=1;x<=y;x++)f[q[x]]=g[x];
    }
  }
  for(i=1;i<=m;i++)printf("%lld ",f[i]);
}

　　

I. Tourists

暴力计算即可。时间复杂度$O(n\log^2n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=220000;
int n,i,j,x,y,g[N],v[N<<1],nxt[N<<1],ed;long long ans;
int size[N],f[N],d[N],son[N],top[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
  size[x]=1;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
    f[v[i]]=x,d[v[i]]=d[x]+1;
    dfs(v[i]),size[x]+=size[v[i]];
    if(size[v[i]]>size[son[x]])son[x]=v[i];
  }
}
void dfs2(int x,int y){
  top[x]=y;
  if(son[x])dfs2(son[x],y);
  for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
}
inline int lca(int x,int y){
  for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y);
  return d[x]<d[y]?d[x]:d[y];
}
int main(){
  scanf("%d",&n);
  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
  dfs(1);
  dfs2(1,1);
  for(i=1;i<=n;i++)for(j=i+i;j<=n;j+=i){
    ans+=d[i]+d[j]-2*lca(i,j)+1;
  }
  printf("%lld",ans);
}

　　

J. Whiteboard

首先用set倒着处理出每个点最后一次被经过的时间，对于每个点计算答案区间，然后求交即可。

时间复杂度$O(n^2\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000020;
typedef long long LL;
char s[1000200];
int n,m,q;
int debug;
set<int>sx[Maxn],sy[Maxn];
int d[Maxn],op[Maxn];
int di[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int getop(char* ss){
	if(ss[0]=='u')return 0;
	if(ss[0]=='r')return 1;
	if(ss[0]=='d')return 2;
	if(ss[0]=='l')return 3;
	return -1;
}
LL L,R;
char ask(int wh,int ty,int loc){
	if(!ty)swap(loc,wh);
	return s[wh*m+loc];
}
void solve(set<int>&S,int st,int ed,LL tl,int wh,int ty){
	int l=st,r=ed;
	if(l>r)swap(l,r);
	set<int>::iterator it=S.lower_bound(l);
	for(;it!=S.end()&&((*it)<=r);){
		char c=ask(wh,ty,*it);
		if(ty==0){
			sx[*it].erase(sx[*it].lower_bound(wh));
		}
		else{
			sy[*it].erase(sy[*it].lower_bound(wh));
		}
		//if(debug)printf("wh=%d ty=%d loc=%d c=%c\n",wh,ty,*it,c);
		if(c=='#')L=max(L,tl-abs((*it)-st));
		else R=min(R,tl-abs((*it)-st)-1);
		S.erase(it++);
	}
}
int main(){
	while(scanf("%d%d%d",&n,&m,&q)!=EOF){
		for(int i=0;i<n;i++){
			scanf("%s",s+(i*m));
		}
		//printf("%s\n",s);
		//printf("%c\n",s[35]);
		for(int i=0;i<n;i++){
			sx[i].clear();
			for(int j=0;j<m;j++)sx[i].insert(j);
		}
		for(int i=0;i<m;i++){
			sy[i].clear();
			for(int j=0;j<n;j++)sy[i].insert(j);
		}
		for(int i=0;i<q;i++){
			char tmp[10];
			scanf("%s%d",tmp,d+i);
			op[i]=getop(tmp);
		}
		int curx=n-1,cury=0;
		LL tl=1;
		for(int i=0;i<q;i++){
			curx+=di[op[i]][0]*d[i];
			cury+=di[op[i]][1]*d[i];
			tl+=d[i];
		}
		L=0,R=tl;
		//printf("curx=%d cury=%d tl=%lld\n",curx,cury,tl);
		for(int i=q-1;i>=0;i--){
			int top=(op[i]+2)%4;
			if(i==1)debug=1;else debug=0;
			int nx=curx+di[top][0]*d[i],ny=cury+di[top][1]*d[i];
			//printf("ny=%d\n",ny);
			if(top==0||top==2)solve(sy[ny],curx,nx,tl,ny,0);
			else solve(sx[nx],cury,ny,tl,nx,1);
			tl-=d[i];
			curx=nx;
			cury=ny;
			//printf("i=%d L=%lld R=%lld\n",i,L,R);
		}
		for(int i=0;i<n&&L<=R;i++){
			for(set<int>::iterator it=sx[i].begin();it!=sx[i].end();it++){
				if(ask(i,1,*it)=='#'){
					L=R+1;
					break;
				}
			}
		}
		if(L>R)puts("-1 -1");
		else printf("%lld %lld\n",L,R);
	}
}

　　

K. YATP

树分治，然后求出凸壳询问最值即可。

时间复杂度$O(n\log^2n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int N=200010;
inline void up(ll&a,ll b){if(a>b)a=b;}
int n,i,x,y,z,a[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ok[N<<1],ed;
ll ans[N],fin,d[N];
int f[N],son[N],all,now;
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;ok[ed]=1;nxt[ed]=g[x];g[x]=ed;}
struct P{ll k,b;P(){}P(ll _x,ll _y){k=_x,b=_y;}}A[N],q[N];
int B[N],m;
inline double pos(const P&a,const P&b){return ((double)(b.b-a.b))/((double)(a.k-b.k));}
inline bool cmpA(const P&a,const P&b){
  if(a.k==b.k)return a.b<b.b;
  return a.k>b.k;
}
inline bool cmpB(int x,int y){return a[x]<a[y];}
void findroot(int x,int y){
  son[x]=1;f[x]=0;
  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
    findroot(v[i],x);
    son[x]+=son[v[i]];
    if(son[v[i]]>f[x])f[x]=son[v[i]];
  }
  if(all-son[x]>f[x])f[x]=all-son[x];
  if(f[x]<f[now])now=x;
}
void dfs(int x,int y,ll z){
  m++;
  d[x]=z;
  A[m]=P(a[x],z);
  B[m]=x;
  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,z+w[i]);
}
inline ll cal(int x,int y){
  return q[y].k*a[x]+d[x]+q[y].b;
}
void solve(int x){
  int i,h=1,t;
  m=0;
  dfs(x,0,0);
  sort(A+1,A+m+1,cmpA);
  sort(B+1,B+m+1,cmpB);
  q[t=1]=A[1];
  for(i=2;i<=m;i++)if(A[i].k!=A[i-1].k){
    while(t>1&&pos(q[t-1],q[t])>pos(q[t],A[i]))t--;
    q[++t]=A[i];
  }
  for(i=1;i<=m;i++){
    while(h<t&&cal(B[i],h)>cal(B[i],h+1))h++;
    ans[B[i]]=min(ans[B[i]],cal(B[i],h));
  }
  for(i=g[x];i;i=nxt[i])if(ok[i]){
    ok[i^1]=0;
    f[0]=all=son[v[i]];
    findroot(v[i],now=0);
    solve(now);
  }
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]);
  for(ed=i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
  for(i=1;i<=n;i++)ans[i]=inf;
  f[0]=all=n;
  findroot(1,now=0);
  solve(now);
  for(i=1;i<=n;i++)fin+=ans[i];
  printf("%lld",fin);
}

　　

---

总结：

• G题poursoul打错样例却不检查样例，盲目调试，下次要注意。