为什么 Markdown 一会儿好一会儿炸的……
今天题不会打，先占个坑。
A
首先我是一个智障。
分析题目完后，发现既然是单向边，且指向根，不如考虑把边反向。
把边反向后，我们就可以得到一个朴素的 DP。
设 f_i 表示从 i 到根所花费的最小钱数。
那么有转移方程 $fi=\min{d_i-d_j \leq k_t}(f_j+w_t)，其中d表示深度，t$ 表示当前节点可选的过路券下标。
此时我们得到了一个期望得分 80pts 的普通算法。
考虑优化这个式子。
自然是优化求 \min_{d_i-d_j \leq k_t}(f_j+w_t) 的过程，一种思路是倍增去向上跳，另一种思路就是用线段树维护 min f_j。
时间复杂度 O(n \log n + q)，实测可能差不多。(甚至线段树还跟快一点)
/*
(Standard IO)
时间限制: 1 s 空间限制: 128 MB
*/
#include
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
typedef long long LL;
typedef pair PII;
#define k first
#define w second
int n,m,d[N],f[N];
int h[N],e[N],ne[N],idx;
void read(int &x)
{
x=0;
int f=1;
char c=getchar();
while(c'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int tr[N<<2];
void pushup(int u){tr[u]=min(tr[u<<1],tr[u<>1;
build(u<<1,l,mid);
build(u<>1;
if(x<=mid)modify(u<<1,l,mid,x,v);
else modify(u<R)return INF;
if(L<=l&&r>1,res=INF;
if(L<=mid)res=min(res,query(u<<1,l,mid,L,R));
if(mid<R)res=min(res,query(u<<1|1,mid+1,r,L,R));
return res;
}
vectorp[N];
void dfs(int u,int father)
{
d[u]=d[father]+1;
if(u==1)f[u]=0;
else
{
for(auto item:p[u])f[u]=min(f[u],query(1,1,n,max(d[u]-item.k,1),d[u]-1)+item.w);
}
modify(1,1,n,d[u],f[u]);
for(int i=h[u];~i;i=ne[i])dfs(e[i],u);
}
int main()
{
memset(f,0x3f,sizeof f);
memset(h,-1,sizeof h);
read(n),read(m);
build(1,1,n);
for(int i=1;i<n;i++)
{
int a,b;
read(a),read(b);
add(b,a);
}
for(int i=1;i<=m;i++)
{
int v,k,w;
read(v),read(k),read(w);
p[v].push_back({k,w});
}
dfs(1,0);
int T;
read(T);
while(T--)
{
int x;
read(x);
printf("%d\n",f[x]);
}
return 0;
}
B
C
所以它到底算结论题还是数学题呢（？
首先特判没有在 T 附近左右横跳的（即走了 n 步还没有到 T 附近的）
然后对于左右横跳的，我们知道坐标处于 [T-x,T+y)
这一区间共有 (x+y) 个数。
然后我们设向左跳动了 a 步，向右即走了 n-a 步。
那么最后我们的终点是 S-ax+(n-a)y
拆开之后就有 S-ax+ny-ay 也就是 S+ny-a(x+y)
考虑这一个数对 x+y 取模，其实就是 s+ny 对 x+y 取模。
由于 [T-x,T+y) 这一区间共有 (x+y) 个数，因此模 x+y 后是唯一的，因此我们就可以直接算出答案。
#include
using namespace std;
typedef __int128 LL;
LL n,s,t,x,y;
void read(LL &x)
{
x=0;
int f=1;
char c=getchar();
while(c'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
void write(LL x)
{
if(x9)write(x/10);
putchar(x%10+'0');
}
void work()
{
read(n),read(s),read(t),read(x),read(y);
if(s+n*y=t)
{
write(s-n*x);
puts("");
return;
}
LL pos=(s+n*y)%(x+y),Lp=(t-x)%(x+y);
pos=(pos+x+y)%(x+y);
Lp=(Lp+x+y)%(x+y);
if(pos>=Lp)write(t-x+pos-Lp);
else write(t+y-Lp+pos);
puts("");
}
int main()
{
freopen("never.in","r",stdin);
freopen("never.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)work();
return 0;
}