Wuyanru's blog
0%

[QOJ9416] Intersection of Paths

发表于 分类于 ，

想到了关键结论，但我并没有意识到这有用。

题目链接。

题意

有一棵 个点的树，边有边权。

现在有 次询问，每一次询问给定 ，你需要先将第 条边的边权改为 。

然后你需要在树上选出 个不同点 ，他们组成了 条路径，第 条路径是 。

定义这个方案的权值是，同时被这 条路径覆盖的边的边权和，需要求出最大权值。

询问之间，边权的修改是独立的。

。

题解

首先可以发现，最后被计入答案的部分一定是一段路径，因为它是若干条路径的交。

先来单独考虑一条边，什么时候能被计入答案，假设这条边左右两侧连通块大小分别为 。

那么可以发现，这条边可能被计入答案当且仅当 。

再来考虑一条路径什么时候能同时被覆盖。

思考可知，一条路径能被覆盖，当且仅当所有的边都满足上述条件。

必要性显然。

充分性的话，考虑这条路径首尾的两条边即可。

也就是说，如果我们只把满足条件的边拿出来，询问相当于要求出这个部分的直径。

那么这个题就好做了，直接将所有询问按照从大到小排序，然后使用在欧拉序上建线段树，维护整棵树的直径即可。

需要支持的操作是区间加和查询深度。

时间复杂度是 。

这里有一个细节，注意到满足条件的边一定是一个连通块。

所以直接将连通块之外的边当成 ，然后维护整棵树直径即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
template<const int N,const int M>
struct graph
{
    int head[N+5];
    int ww[M+5];
    int t[M+5];
    int x[M+5];
    int cntm;
    graph(){ cntm=1;}
    inline void clear(int n=N)
    {
        cntm=1;
        for(int i=1;i<=n;i++) head[i]=0;
    }
    inline void ad(int u,int v,int w=0)
    {
        cntm++;
        t[cntm]=v;
        x[cntm]=head[u];
        ww[cntm]=w;
        head[u]=cntm;
    }
    inline void add(int u,int v,int w=0)
    {
        ad(u,v,w);
        ad(v,u,w);
    }
    inline int st(int num){ return head[num];}
    inline int to(int num){ return t[num];}
    inline int nx(int num){ return x[num];}
    inline int w(int num){ return ww[num];}
};
graph<500000,1000000>g;
struct node
{
    int u,v,w;
}e[500001],a[500001];
struct nod
{
    ll mi,ma;
    ll s1,s2,sum;
    inline void add(ll y)
    {
        mi+=y,ma+=y;
        s1-=y,s2-=y;
    }
}num[4000001];
ll tag[4000001];
int st[500001],ed[500001];
int siz[500001],fa[500001];
vc<int>eid[500001];
vc<int>qid[500001];
bool vis[500001];
ll qans[500001];
int n,m,c;
void dfs(int num)
{
    siz[num]=1,st[num]=++c;
    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(p==fa[num]) continue;
        fa[p]=num,dfs(p),siz[num]+=siz[p],c++;
    }
    ed[num]=c;
}
nod operator + (nod a,nod b)
{
    nod ans;
    ans.mi=min(a.mi,b.mi);
    ans.ma=max(a.ma,b.ma);
    ans.s1=max(max(a.s1,b.s1),a.ma-2*b.mi);
    ans.s2=max(max(a.s2,b.s2),-2*a.mi+b.ma);
    ans.sum=max(max(a.sum,b.sum),max(a.s1+b.ma,a.ma+b.s2));
    return ans;
}
inline void push_up(int p){ num[p]=num[p*2]+num[p*2|1];}
inline void T(int p,ll y)
{
    num[p].add(y);
    tag[p]+=y;
}
inline void push_down(int p)
{
    T(p*2,tag[p]),T(p*2|1,tag[p]);
    tag[p]=0;
}
void add(int p,int pl,int pr,int l,int r,ll y)
{
    if(l<=pl&&pr<=r){ T(p,y);return ;}
    int mid=(pl+pr)>>1;push_down(p);
    if(l<=mid) add(p*2,pl,mid,l,r,y);
    if(mid<r) add(p*2|1,mid+1,pr,l,r,y);
    push_up(p);
}
inline void add(int u,ll w)
{
    // printf("add %d %lld [%d,%d]\n",u,w,st[u],ed[u]);
    add(1,1,c,st[u],ed[u],w);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<n;i++) 
    {
        e[i].u=read(),e[i].v=read(),e[i].w=read();
        g.add(e[i].u,e[i].v);
    }
    dfs(1);
    for(int i=1;i<n;i++)
    {
        if(fa[e[i].v]==e[i].u) swap(e[i].u,e[i].v);
        eid[min(siz[e[i].u],n-siz[e[i].u])].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        a[i].u=read(),a[i].v=read(),a[i].w=read();
        qid[a[i].w].push_back(i);
    }
    for(int i=n;i;i--)
    {
        //先加入边
        for(int j:eid[i])
        {
            add(e[j].u,e[j].w);
            vis[j]=1;
        }
        //处理查询
        for(int j:qid[i])
        {
            ll val=0;
            if(vis[a[j].u])
            {
                val=a[j].v-e[a[j].u].w;
                add(e[a[j].u].u,val);
            }
            // printf("query %d\n",j);
            qans[j]=num[1].sum;
            add(e[a[j].u].u,-val);
        }
    }
    for(int i=1;i<=m;i++) printf("%lld\n",qans[i]);
    return 0;
}