题目描述
Lass给你出了一道倒闭题：
给你一个n个点的树还有一只青蛙。
由于这棵树被夺去了生命，所以你需要通过青蛙来复活上面的节点，有m次操作。
每次操作有三个参数a,b,t
然后会给你a条链，青蛙都会把每条链上面的所有点增加一秒
然后会给你b个点，青蛙都会把每个点子树里面的所有点增加一秒
注意青蛙是大公无私的，所以每次牠不会管这个节点之前有没有增加过，都会增加一秒
但是因为树失去了生命太多了，所以只有被增加了>=t秒的节点会重获新生（t可以为0）
而且因为你的黑框眼镜是假的，所以每次的操作是独立的
也就是说，每次操作增加的秒数，在这次操作结束的瞬间就会被青蛙回收，这棵树的所有节点又会失去生命
多么残酷的一道题啊
输入输出格式
输入格式：
第一行二个数n,m
之后n-1行每行两个数x,y表示x和y直接连有边
之后m次操作
每次操作先是一行三个数a,b,t,意义已上述
之后a行每行两个数x,y表示青蛙从x跳到y，每个节点增加了1s
之后b行每行一个数x表示青蛙把x的子树里面每个节点增加了1s
输出格式：
m行，第i行一个数表示第i次操作有多少个节点获得了新生
输入输出样例
输入样例#1：
5 2
1 2
2 3
3 4
4 5
1 1 2
2 3
3
1 2 2
1 3
2
5
输出样例#1：
1 3
输入样例#2：
5 2
1 2
2 3
2 4
3 5
2 3 3
2 3
3 3
3
3
3
4 2 3
1 4
2 3
4 5
1 2
4
3
分析
树链剖分+扫描线+优化
首先我要投诉洛谷
这题面写的太恶心了
@lin_toto
= =
题意：有两种操作，树上路径整体+1和子树+1
那么树链剖分
但是再接个扫描线发现会TLE：因为朴素扫描线结果是O(nm)
所以扫描线就不扫描每个点了，而是扫描每次区间差分修改的端点
最后卡个常
注意 t 有可能为0
因此写的时候要注意 1 到 第一个端点 符合条件的情况
代码
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define maxn 500010 5 using namespace std; 6 7 int n,m,TIM,cnt,siz[maxn],top[maxn],tid[maxn],fa[maxn],son[maxn],depth[maxn],End[maxn],line[maxn],q[maxn*20]; 8 9 struct edge{ 10 int from,v; 11 }e[maxn]; int tot,first[maxn]; 12 inline void insert(int u,int v){ tot++; e[tot].from = first[u]; e[tot].v = v; first[u] = tot; } 13 14 inline void dfs(int now){ 15 siz[now] = 1; 16 for(register int i = first[now];i;i = e[i].from){ 17 int v = e[i].v; 18 if(v != fa[now]){ 19 depth[v] = depth[now]+1; 20 fa[v] = now; 21 dfs(v); 22 siz[now] += siz[v]; 23 if(!son[now] || siz[v] > siz[son[now]]) 24 son[now] = v; 25 } 26 } 27 } 28 29 inline void dfs2(int now,int t){ 30 top[now] = t; 31 tid[now] = ++TIM; 32 if(!son[now]){ End[now] = TIM; return; } 33 dfs2(son[now],t); 34 for(register int i = first[now];i;i = e[i].from){ 35 int v = e[i].v; 36 if(v != fa[now] && v != son[now]) 37 dfs2(v,v); 38 }End[now] = TIM; 39 } 40 41 inline void Lineup(int l,int r){ 42 q[++cnt] = l; 43 q[++cnt] = r+1; 44 line[l]++,line[r+1]--; 45 } 46 47 inline void Jump(int u,int v){ 48 if(depth[top[u]] < depth[top[v]]) swap(u,v); 49 while(top[u] != top[v]){ 50 Lineup(tid[top[u]],tid[u]); 51 u = fa[top[u]]; 52 if(depth[top[u]] < depth[top[v]]) swap(u,v); 53 }if(depth[u] > depth[v]) swap(u,v); 54 Lineup(tid[u],tid[v]); 55 } 56 57 inline void Cover(int u){ 58 Lineup(tid[u],End[u]); 59 } 60 61 inline void Conc(int t){ 62 q[++cnt] = n+1; q[++cnt] = 1; 63 long long sum = 0,ans = 0; 64 sort(q+1,q+1+cnt); 65 cnt = unique(q+1,q+1+cnt)-q-1; 66 for(register int i = 1;i < cnt;i++){ 67 while(q[i+1] == q[i] && i+1 < cnt) i++; 68 sum += line[q[i]]; 69 line[q[i]] = 0; 70 if(sum >= t) ans += q[i+1]-q[i]; 71 }q[cnt] = cnt = 0; printf("%d ",ans); 72 } 73 74 inline void read(int &ans){ 75 int t = 1; ans = 0; char ctr = getchar(); 76 while(ctr < '0' || ctr > '9') ctr=='-'&&(t = -1),ctr = getchar(); 77 while(ctr >= '0' && ctr <= '9') ans = ans*10+ctr-'0',ctr = getchar(); 78 ans *= t; 79 } 80 81 int main(){ 82 int u,v,a,b,t; 83 // scanf("%d%d",&n,&m); 84 read(n); read(m); 85 for(register int i = 1;i < n;i++){ 86 // scanf("%d%d",&u,&v); 87 read(u),read(v); 88 insert(u,v); insert(v,u); 89 }depth[1] = 1; dfs(1); dfs2(1,1); 90 91 while(m--){ 92 // scanf("%d%d%d",&a,&b,&t); 93 read(a); read(b); read(t); 94 while(a--){ read(u),read(v);/*scanf("%d%d",&u,&v);*/ Jump(u,v); } 95 while(b--){ read(u); /*scanf("%d",&u);*/ Cover(u); } 96 Conc(t); 97 } 98 99 return 0; 100 }