题目链接:
题目大意：链更新。链查询，求树链的最大子段和。（子段可以为空）
解题思路：
将所有Query离线存储，并且注明哪个是更新，哪个是查询。
Tarjan离线处理中，记录每个结点的前驱，p[v]=u。
若更新，从u点回溯到LCA，从v点回溯到LCA，逐个修改。
若查询，将u点回溯到LCA，LCA，v点回溯到LCA的倒序拼成一个序列，求最大子段和。
值得注意的是，子段和全为负值的时候，ans=max(0,ans)，即不要任何插线板（原题意思不明)。
#include "cstdio"#include "cstring"#include "vector"#include "algorithm"using namespace std;#define maxn 100005#define inf 0x3f3f3f3fint head[maxn],qhead[maxn],lag[maxn],kth[maxn],tot1,tot2,f[maxn],vis[maxn],ancestor[maxn],p[maxn],s1[maxn],s2[maxn];bool isUpdate[maxn];struct Edge{ int to,next;}e[maxn*2];struct Query{ int from,to,next,idx,c;}q[maxn*2];void addedge(int u,int v){ e[tot1].to=v; e[tot1].next=head[u]; head[u]=tot1++;}void addquery(int u,int v,int idx,int c=inf){ q[tot2].from=u; q[tot2].to=v; q[tot2].next=qhead[u]; q[tot2].idx=idx; if(c!=inf) q[tot2].c=c; qhead[u]=tot2++;}int find(int x) { return x!=f[x]?f[x]=find(f[x]):x;}void Union(int u,int v){ u=find(u),v=find(v); if(u!=v) f[v]=u;}void LCA(int u){ vis[u]=true; f[u]=u; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(!vis[v]) { p[v]=u; LCA(v); Union(u,v); } } for(int i=qhead[u];i!=-1;i=q[i].next) { int v=q[i].to; if(vis[v]) ancestor[q[i].idx]=find(v); //or storage e[i].lca=e[i^1].lca=find(v) }}int sum(int num){ s2[0]=s1[0]; int Max=s2[0]; for(int i=1; i 0) s2[i]=s2[i-1]+s1[i]; else s2[i]=s1[i]; if(s2[i]>Max) Max=s2[i]; } return max(0,Max);}int main(){ //freopen("in.txt","r",stdin); int T,n,m,u,v,c,cmd,qcnt=0; scanf("%d",&n); tot1=tot2=0; memset(head,-1,sizeof(head)); memset(qhead,-1,sizeof(qhead)); memset(vis,0,sizeof(vis)); memset(isUpdate,0,sizeof(isUpdate)); for(int i=1;i<=n;i++) scanf("%d",&lag[i]); for(int i=0; i