题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3872
可以倒推出每个叶子节点可以接受的值域。然后每个叶子二分有多少个区间符合即可。
注意一开始的两个点不是直接是 l[ u ]=r[ u ]=lm !也要看度数的!且把那条边的两个端点分别算子树很方便。
而且过程中似乎会爆 long long ,所以如果 l[ i ] 都大于最大值就不往下算了;r[ i ]也要每次与最大值取min。
然后是和网上一份题解对拍出错却仍A了此题的代码。不想管是哪错了……
(连freopen都忘了去掉也能A!)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e6+5; int n,m,lm,a[N],hd[N],xnt,to[N<<1],nxt[N<<1]; int rt1,rt2,deg[N]; ll l[N],r[N],ans; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void add(int x,int y) { to[++xnt]=y; nxt[xnt]=hd[x]; hd[x]=xnt; to[++xnt]=x; nxt[xnt]=hd[y]; hd[y]=xnt; deg[x]++; deg[y]++; } void dfs(int cr,int fa) { //printf("l[%d]=%lld r[%d]=%lld ",cr,l[cr],cr,r[cr]); for(int i=hd[cr],v;i;i=nxt[i]) if(i>2&&(v=to[i])!=fa) { if(deg[v]==1) { l[v]=l[cr]; r[v]=r[cr]; } else { l[v]=l[cr]*(deg[v]-1); r[v]=r[cr]*(deg[v]-1)+deg[v]-2; } r[v]=min(r[v],(ll)a[m]);/// if(l[v]>a[m])continue;/// dfs(v,cr); } } int findr(ll x)//ll { int l=1,r=m,ret=0; while(l<=r) { int mid=l+r>>1; if(a[mid]<=x)ret=mid,l=mid+1; else r=mid-1; } return ret; } int findl(ll x) { int l=1,r=m,ret=m+1; while(l<=r) { int mid=l+r>>1; if(a[mid]>=x)ret=mid,r=mid-1; else l=mid+1; } return ret; } int main() { freopen("data.in","r",stdin); n=rdn(); m=rdn(); lm=rdn(); for(int i=1;i<=m;i++) a[i]=rdn(); sort(a+1,a+m+1); int u,v; u=rdn(); v=rdn(); rt1=u; rt2=v; add(u,v); // l[u]=r[u]=l[v]=r[v]=lm; for(int i=2;i<n;i++) { u=rdn(); v=rdn(); add(u,v); } u=rt1; v=rt2; if(deg[u]==1) l[u]=r[u]=lm;///// else l[u]=lm*(deg[u]-1),r[u]=lm*(deg[u]-1)+deg[u]-2;/// r[u]=min(r[u],(ll)a[m]); if(l[u]<=a[m]) dfs(u,0); if(deg[v]==1) l[v]=r[v]=lm; else l[v]=lm*(deg[v]-1),r[v]=lm*(deg[v]-1)+deg[v]-2; r[v]=min(r[v],(ll)a[m]); if(l[v]<=a[m]) dfs(v,0); for(int i=1;i<=n;i++) if(deg[i]==1&&r[i]&&l[i]<=a[m]) ans+=findr(r[i])-findl(l[i])+1; printf("%lld ",ans*lm); return 0; }