T1
显然贪心+维护小根堆；
注意边界条件，以及一些细节问题
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define LL long long
using namespace std;
const int N=3e5+7;
struct node{
LL v,w,cha;
int id;
friend bool operator <(const node x,const node y){
return x.cha>y.cha;
}
}a[N];
int n,k,ans=1<<30;
priority_queue<node> q;
int cmp(node x,node y){
if(x.v==y.v) return x.id<y.id;
return x.v>y.v;
}
int main(){
freopen("rank.in","r",stdin);
freopen("rank.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i].v,&a[i].w);
a[i].cha=a[i].w-a[i].v;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(a[i].id==1){
k=i;
break;
}
}
for(int i=1;i<=n;i++){
if(a[i].v>a[k].v) q.push(a[i]);
else break;
}
int num=k+1;
LL sum=a[k].v;
ans=(int)q.size()+1;
a[n+1].v=-1;
while(1){
node now=q.top();
if(sum==0) break;
if(sum<now.cha+1) break;
sum-=(now.cha+1);
q.pop();
for(int i=num;i<=n;i++){
if(a[i].v>sum){
q.push(a[i]);
if(i==n) num=n+1;
}
else{
num=i;
break;
}
}
ans=min(ans,(int)q.size()+1);
if(ans==1) break;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
/*
8
20 1000
32 37
40 1000
45 50
16 16
16 16
14 1000
2 1000
8
40 1000
32 37
40 42
45 50
16 16
16 16
14 1000
2 1000
10
25 38
45 48
9 13
49 50
12 14
41 42
34 37
46 49
14 15
23 26
*/
T2
由于是对链进行操作所以考虑树上查分；
又因为双向边，对答案影响不同，所以要分别算，
还有这题比较坑，注意体面
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N=1e5+7;
const int p=1e9+7;
struct edge{
int v,id,nxt;
}e[N<<1];
int n,cnt=1,m,maxn;
LL ans;
int a[N],fa[N],head[N],dep[N],top[N],siz[N],hs[N],f[N],d[N],ba[N];
void add_edge(int u,int v,int w){
e[++cnt]=(edge){v,w,head[u]};
head[u]=cnt;
}
void get_tree(int u){
dep[u]=dep[fa[u]]+1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].v;
if(to!=fa[u]){
fa[to]=u;
get_tree(to);
siz[u]+=siz[to];
if(siz[hs[u]]<siz[to]) hs[u]=to;
}
}
}
void dfs(int u,int fat){
top[u]=fat;
if(hs[u]) dfs(hs[u],fat);
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].v;
if(to!=fa[u]&&to!=hs[u]){
dfs(to,to);
}
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void dfs1(int u){
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].v;
if(to!=fa[u]){
dfs1(to);
f[u]+=f[to];
d[u]+=d[to];
}
}
maxn=max(maxn,max(f[u],d[u]));
}
void dfs2(int u){
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].v;
if(to!=fa[u]){
if(e[i].id==1){
ans+=ba[d[to]]-1;
}else{
if(e[i^1].id==1){
ans+=ba[f[to]]-1;
}
}
dfs2(to);
}
}
}
int main(){
freopen("task.in","r",stdin);
freopen("task.out","w",stdout);
n=read();
for(int i=1;i<n;i++){
int x,y,z;
x=read();
y=read();
z=read();
add_edge(x,y,0);
add_edge(y,x,z);
}
get_tree(1);
dfs(1,1);
// return 0;
scanf("%d",&m);
for(int i=1;i<=m;i++){
a[i]=read();
}
a[0]=1;
for(int i=1;i<=m;i++){
int x=a[i-1];
int y=a[i];
int ff=lca(x,y);
// cout<<ff<<"
";
f[x]++;
d[y]++;
f[ff]--;
d[ff]--;
}
dfs1(1);
// for(int i=1;i<=n;i++){
// cout<<i<<" "<<f[i]<<" "<<d[i]<<"
";
// }
// cout<<"----"<<maxn<<"
";
ba[0]=1;
for(int i=1;i<=maxn+1;i++){
ba[i]=1LL*ba[i-1]*2%p;
}
// for(int i=1;i<=maxn;i++){
// cout<<sum[i]<<"
";
// }
// for(int u=1;u<=n;u++){
// for(int i=head[u];i;i=e[i].nxt){
// int to=e[i].v;
// if(e[i].id==1){
//// cout<<u<<" "<<to<<" "<<dep[u]<<" "<<dep[to]<<"
";
// int tt=dep[u]>dep[to]?u:to;
// if(dep[u]<dep[to]){
// ans=(1LL*ans+ba[d[tt]]-1)%p;
// }else ans=(1LL*ans+ba[f[tt]]-1)%p;
//// cout<<ans<<"
";
// }
// }
// }
dfs2(1);
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
/*
5
1 2 0
2 3 0
5 1 1
3 4 1
5
5 4 5 2 2
*/